二分查找又称折半搜索算法。 狭义地来讲，二分查找是一种在有序数组查找某一特定元素的搜索算法。这同时也是大多数人所知道的一种说法。实际上， 广义的二分查找是将问题的规模缩小到原有的一半。类似的，三分法就是将问题规模缩小为原来的 1/3。
对于搜索类题目，解空间一定是有限的，不然问题不可解。对于搜索类问题，第一步就是需要明确解空间，这样你才能够在解空间内进行搜索。这个技巧不仅适用于二分法，只要是搜索问题都可以使用，比如 DFS，BFS 以及回溯等。只不过对于二分法来说，明确解空间显得更为重要。
定义解空间的时候的一个原则是： 可以大但不可以小。因为如果解空间偏大（只要不是无限大）无非就是多做几次运算，而如果解空间过小则可能错失正确解，导致结果错误。
有的序列有序题目直接讲出来了，会比较容易。而有些则隐藏在题目信息之中。乍一看，题目并没有有序关键字，而有序其实就隐藏在字里行间。比如题目给了数组 nums，并且没有限定 nums 有序，但限定了 nums 为非负。这样如果给 nums 做前缀和或者前缀或（位运算或），就可以得到一个有序的序列啦。
虽然二分法不意味着需要序列有序，但大多数二分题目都有有序这个显著特征。只不过：
- 有的是题目直接限定了有序。这种题目通常难度不高，也容易让人想到用二分。
- 有的是需要你自己构造有序序列。这种类型的题目通常难度不低，需要大家有一定的观察能力。
堆的一种很重要的用法是求第 k 大的数，而二分法也可以求第 k 大的数，只不过二者的思路完全不同。使用堆求解可以应用大(小)根堆的方法。那么二分呢？
例题：给定一个数组 nums，让你求 nums 第 k 大的任意两个数的差的绝对值。
分析：对于本道题，解空间就是 [0, max(nums) - min(nums)]。明确了解空间之后，我们需要对解空间进行二分。可以选当前解空间的中间值 mid ，然后计算小于等于这个中间值的任意两个数的差的绝对值有几个，我们不妨令这个数字为 x。
- 如果 x 大于 k，那么解空间中大于等于 mid 的数都不可能是答案，可以将其舍弃。
- 如果 x 小于 k，那么解空间中小于等于 mid 的数都不可能是答案，可以将其舍弃。
- 如果 x 等于 k，那么 mid 就是答案。
class Solution {
public int solve(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, right = nums[nums.length - 1] - nums[0];
while(left <= right) {
int mid = (left + right) / 2;
if (count_not_greater(mid, nums) >= k) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
private int count_not_greater(int diff, int[] nums) {
int i = 0, ans = 0;
for(int j = 0; j < nums.length; j ++){
while(nums[j] - nums[i] > diff) {
i ++;
}
ans += j - i;
}
return ans;
}
}显然折半的难点是根据什么条件舍弃哪一步部分。这里有两个关键字:
- 什么条件
- 舍弃哪部分
给定一个由数字组成的有序数组 nums，并给你一个数字 target。问 nums 中是否存在 target。如果存在， 则返回其在 nums 中的索引。如果不存在，则返回 - 1。
这是二分查找中最简单的一种形式。当然二分查找也有很多的变体，这也是二分查找容易出错，难以掌握的原因。
常见变体有：
- 如果存在多个满足条件的元素，返回最左边满足条件的索引。
- 如果存在多个满足条件的元素，返回最右边满足条件的索引。
- 数组不是整体有序的。 比如先升序再降序，或者先降序再升序。
- 将一维数组变成二维数组。
- 数组是有序的（如果无序，我们也可以考虑排序，不过要注意排序的复杂度）
算法描述：
- 先从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
- 如果目标元素大于中间元素，那么数组中小于中间元素的值都可以排除（由于数组有序， 那么相当于是可以排除数组左侧的所有值），解空间可以收缩为 [mid+1, r]。
- 如果目标元素小于中间元素，那么数组中大于中间元素的值都可以排除（由于数组有序， 那么相当于是可以排除数组右侧的所有值），解空间可以收缩为 [l, mid - 1]。
- 如果在某一步骤解空间为空，则代表找不到。
复杂度分析
由于这种搜索算法每一次比较都使搜索范围缩小一半，是典型的二分查找。
- 平均时间复杂度： O(logN)
- 最坏时间复杂度： O(logN)
- 空间复杂度
- 迭代: O(1)
- 递归: O(logN)
首先定义解空间为 [left, right]，注意是左右都闭合，之后会用到这个点
-
由于定义的解空间为 [left, right]，因此当 left <= right 的时候，解空间都不为空 ，此时我们都需要继续搜索。 也就是说终止搜索条件应该为 left <= right。
-
循环体内，我们不断计算 mid ，并将 nums[mid] 与 目标值比对。
- 如果 nums[mid] 等于目标值， 则提前返回 mid（只需要找到一个满足条件的即可）
- 如果 nums[mid] 小于目标值， 说明目标值在 mid 右侧，这个时候解空间可缩小为 [mid + 1, right] （mid 以及 mid 左侧的数字被我们排除在外）
- 如果 nums[mid] 大于目标值， 说明目标值在 mid 左侧，这个时候解空间可缩小为 [left, mid - 1] （mid 以及 mid 右侧的数字被我们排除在外）
-
循环结束都没有找到，则说明找不到，返回 -1 表示未找到。
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
if (nums[mid] < target)
// 解空间变为 [mid+1, right]
left = mid + 1;
if (nums[mid] > target)
// 解空间变为 [left, mid - 1]
right = mid - 1;
}
return -1;
}上面我们讲了寻找满足条件的值。如果找不到，就返回 -1。那如果不是返回 -1，而是返 回应该插入的位置，使得插入之后列表仍然有序呢？
比如一个数组 nums: [1,3,4]，target 是 2。我们应该将其插入（注意不是真的插入）的 位置是索引 1 的位置，即 [1,2,3,4]。因此寻找最左插入位置应该返回 1， 而寻找满足条件的位置 应该返回-1。
另外如果有多个满足条件的值，我们返回最左侧的。 比如一个数组 nums: [1,2,2,2,3,4]，target 是 2，我们应该插入的位置是 1。
等价于寻找最左满足 >= target 的位置。
具体算法：
-
首先定义解空间为 [left, right]，注意是左右都闭合。
-
由于我们定义的解空间为 [left, right]，因此当 left <= right 的时候，解空间都不为空。 也就是说我们的终止搜索条件为 left <= right。
-
当 A[mid] >= x，说明找到一个备选值，我们令 r = mid - 1 将 mid 从解空间排除，继续看看有没有更好的备选值。
-
当 A[mid] < x，说明 mid 根本就不是答案，直接更新 l = mid + 1，从而将 mid 从解空间排除。
-
最后解空间的 l 就是最好的值。
等价于寻找最右满足 <= target 的位置的右邻居。
具体算法：
-
首先定义解空间为 [left, right]，注意是左右都闭合。
-
由于我们定义的解空间为 [left, right]，因此当 left <= right 的时候，解空间都不为空。 也就是说我们的终止搜索条件为 left <= right。
-
当 A[mid] > x，说明找到一个备选值，我们令 r = mid - 1 将 mid 从解空间排除，继续看看有没有更好的备选值。
-
当 A[mid] <= x，说明 mid 根本就不是答案，直接更新 l = mid + 1，从而将 mid 从解空间排除。
-
最后解空间的 l 就是最好的值。
对于二分题目首先要明确解空间，然后根据一定条件（通常是和中间值比较），舍弃其中一半的解。大家可以先从查找满足条件的值的二分入手，进而学习最左和最右二分。同时大家只需要掌握最左和最右二分即可，因为后者功能大于前者。
对于最左和最右二分，简单用两句话总结一下：
- 最左二分不断收缩右边界，最终返回左边界
- 最右二分不断收缩左边界，最终返回右边界
- 能力检测和计数二分本质差不多，都是 普通二分 的泛化。
- 前缀和二分和插入排序二分，本质都是在构建有序序列。
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(possible(mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
private boolean possible(int mid){
// ...
}对比普通二分，多了个 possible() 函数判断检测能力。
875. 爱吃香蕉的珂珂（中等）
二分解决的关键在于：
- 明确解空间。 对于这道题来说， 解空间就是 [1,max(piles)]。
- 如何收缩解空间。关键点在于如果速度 k 吃不完所有香蕉，那么所有小于等于 k 的解 都可以被排除。
综上，我们可以使用最左二分，即不断收缩右边界。
475. 供暖器 (中等)
778. 水位上升的泳池中游泳（困难）
与能力检测二分大致相同，见如下例题：
719. 找出第 k 小的距离对（困难）
如果数组全是正的，那么其前缀和就是一个严格递增的数组，基于这个特性，可以在其之上做二分。类似的有单调栈/队列。
327. 找出第 k 小的距离对（困难）
除了上面的前缀和之外，我们还可以自行维护有序序列。一般有两种方式：
-
直接对序列排序。
-
遍历过程维护一个新的有序序列，有序序列的内容为已经遍历过的值的集合。