二分查找法
二分查找是一种把空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。
二分查找前提条件是要排好序。
二分查找可以分成3步：
1. 预处理 —— 如果集合未排序，则进行排序。
2. 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
3. 后处理 —— 在剩余空间中确定可行的候选者。
二分查找模板：
模板一：最常用最基本的模板
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}
模板二：二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.length && nums[left] == target) return left;
return -1;
}
关键点：
1. 查找条件需要访问元素的直接右邻居。
2. 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
3. 保证查找空间在每一步中至少有 2 个元素。
4. 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
和模板1不同点：
初始条件：left = 0, right = length
终止：left == right
向左查找：right = mid
向右查找：left = mid+
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xerqxt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
统一模板
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
}
1. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xem7js/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法1：解题思路：此题只要求找到一个峰值就可以。所以只要找到第一个比右侧大的数，该数就是峰值。
class Solution {
public int findPeakElement(int[] nums) { for(int i = 0; i < nums.length - 1; i++) { if(nums[i] > nums[i+1]) { return i; } } return nums.length - 1; } } 方法2： 二分查找法。 class Solution { public int findPeakElement(int[] nums) { int start = 0; int end = nums.length - 1;while(start < end) { int mid = start + (end - start) / 2; if(nums[mid] < nums[mid+1]) { start = mid + 1; } else{ end = mid; } } return start; } } 2. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xenp13/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题思路：二分查找，找到目标值后向两边扩散查找。找出所有的目标值。
class Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[]{-1,-1}; if(nums == null || nums.length == 0) { return result; }int start = 0; int end = nums.length - 1; while(start <= end) { int mid = start + (end - start) / 2; if(nums[mid] > target) { end = mid - 1; continue; } if(nums[mid] < target) { start = mid + 1; continue; }
int back = mid, forward = mid; while(back >= 0) { if(nums[back] == target) { back--; continue; } break; }
while(forward <= end){ if(nums[forward] == target) { forward++; continue; } break; } result[0] = back + 1; result[1] = forward - 1; break; } return result; } } 3. 找到 K 个最接近的元素
给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xeve4m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法1： 解题思路： 二分查找目标值。然后用双指针前后查找，知道找到k个值。
class Solution { public Listwhile(k > 1) { if(pre < 0){ result.add(arr[forward++]); k--; continue; } if(forward >= arr.length) { result.add(arr[pre--]); k--; continue; } if(Math.abs(arr[pre] - x) > Math.abs(arr[forward] - x)) { result.add(arr[forward++]); } else{ result.add(arr[pre--]); } k--; } Collections.sort(result); return result; }
private int findTarget(int[] arr, int target) { int start = 0; int end = arr.length - 1;
while(start <= end) { int mid = start + (end - start) / 2; if(arr[mid] == target) { return mid; } else if(arr[mid] > target) { end = mid - 1; } else { start = mid + 1; } }
if(start >= arr.length) { return arr.length - 1; } if(end < 0) { return 0; } if(Math.abs(arr[start] - target) >= Math.abs(arr[end] - target)) { return end; } else { return start; } } } 方法2：解题思路：把数组转成List，然后按差值进行升序排序，找到前K个元素。 class Solution { public List
4. Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xe7k32/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题思路：利用forkjoin算法，二分计算后再合并相乘。
class Solution { public double myPow(double x, int n) { if(x == 0) { return 0; } return n > 0 ? doPow(x, n) : 1 / doPow(x, n); }private double doPow(double x, int n) { if(n == 0) { return 1; } double result = doPow(x, n/2);
return (n & 1) == 0 ? result * result : result * result * x; } }
5. 寻找比目标字母大的最小字母
给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
示例：
输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f"
输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j"
输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c"
输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xeiuui/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
while(start < end) { int mid = start + (end - start) / 2; if(letters[mid] <= target) { start = mid + 1; } else { end = mid; } } return letters[start];
} }
1011. 在 D 天内送达包裹的能力 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。 示例 1： 输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5 输出：15 解释： 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示： 第 1 天：1, 2, 3, 4, 5 第 2 天：6, 7 第 3 天：8 第 4 天：9 第 5 天：10 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 示例 2： 输入：weights = [3,2,2,4,1,4], D = 3 输出：6 解释： 船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示： 第 1 天：3, 2 第 2 天：2, 4 第 3 天：1, 4 示例 3： 输入：weights = [1,2,3,1,1], D = 4 输出：3 解释： 第 1 天：1 第 2 天：2 第 3 天：3 第 4 天：1, 1 解题思路：货物是按顺序运算的，每次运输的最小运输量就是运输的最大运量。 每日的最大运输量就是总的货物量。用二分查找法找到最小的每日运输量
class Solution { public int shipWithinDays(int[] weights, int D) { int[] goods = getMaxDayLoadAndTotal(weights); int totalWeight = goods[0]; int dayMax = goods[1]; int left = dayMax; int right = totalWeight; int mid = 0; while(left <= right) { mid = left + (right - left) / 2; if(canFinishGoods(weights, D, mid)) { right = mid - 1; } else { left = mid + 1; } } return left; } private int[] getMaxDayLoadAndTotal(int[] weights) { int dayMax = 0; int total = 0; for(int i = 0; i < weights.length; i++) { dayMax = Math.max(dayMax, weights[i]); total += weights[i]; } return new int[]{total, dayMax}; } private boolean canFinishGoods(int[] weights, int day, int load) { boolean canFinish = false; int totalLoad = 0; for(int i = 0 ; i < weights.length; i++) { totalLoad += weights[i]; if(totalLoad > load) { totalLoad = weights[i]; day--; if(day <= 0) { return false; } } } return true; } }
1011. 在 D 天内送达包裹的能力
难度中等传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5 输出：15 解释： 船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示： 第 1 天：1, 2, 3, 4, 5 第 2 天：6, 7 第 3 天：8 第 4 天：9 第 5 天：10 请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], D = 3 输出：6 解释： 船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示： 第 1 天：3, 2 第 2 天：2, 4 第 3 天：1, 4
示例 3：
输入：weights = [1,2,3,1,1], D = 4 输出：3 解释： 第 1 天：1 第 2 天：2 第 3 天：3 第 4 天：1, 1