二分查找细节分析
本篇仅分析二分查找的细节问题，在阅读前请确保已经对“二分查找”概念与步骤有初步了解。
二分查找的三个常用搜索区间
| 搜索区间 | 终止条件 | 左右指针初始赋值 | 左右指针赋值 | 循环条件 |
|---|---|---|---|---|
| 左闭右闭[l,r] | 相错终止 | l=0 r=nums.length-1 | l = mid+1 r = mid-1 | l<=r |
| 左闭右开[l,r) | 相交终止 | l=0 r=nums.length | l = mid+1 r = mid | l<r |
| 左开右开(l,r) | 相邻终止 | l=-1 r=nums.length | l = mid r = mid | l+1<r |
还有左开右闭等搜索区间，在此不再赘述。
以LeetCode704.二分查找为例：
左闭右闭
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return -1;
}
左闭右开
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > target) {
r = mid;
} else if (nums[mid] < target) {
l = mid + 1;
} else {
return mid;
}
}
return -1;
}
左开右开
public int search(int[] nums, int target) {
int l = -1;
int r = nums.length;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > target) {
r = mid;
} else if (nums[mid] < target) {
l = mid;
} else {
return mid;
}
}
return -1;
}
二分查找变体
查找左边界
左边界是指在有序数组中，被搜索数的第一次出现下标。
例如，在数组[5,7,7,8,8,10]中，7的左边界是1,8的左边界是3。
而根据搜索区间，我们可以得到上述三种写法的查找左边界。
下面以左闭右闭为例：
private int getLeft(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
// int leftBoard = -2;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
// leftBoard = r;
}
}
// 检查出界情况
if (l >= nums.length || nums[l] != target) {
return -1;
}
return l;
// return leftBoard;
}
对于左右边界，在这里有个核心问题：为什么当nums[mid] >= target时，r = mid - 1。
从搜索区间来看，每次搜索时，我们都在搜索闭区间[l, r]。如果nums[mid]在>=target时，mid不一定是左边界，此时要迁移右指针，把mid排除出搜索区间。
根据相错终止的思路，最终l会停留在r的右侧，即l = r + 1，如果nums[mid] == target时已经是左边界，那么右指针将不会再挪动，在循环终止时根据l的位置，即可断言：l是左边界。
相应的，可以推理如果写判断条件nums[mid] == target时，l = mid + 1，此时l必定会越过左边界。所以我们要根据右指针返回结果：
private int getLeft(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
// 检查出界情况
if (r + 1 == nums.length || nums[r + 1] != target) {
return -1;
}
return r + 1;
}
但此种方法过于繁琐，所以使用l返回即可。
左闭右开写法：
private int getLeft(int[] nums, int target) {
int l = 0;
int r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
// 检查出界情况
if (l >= nums.length || nums[l] != target) {
return -1;
}
return l;
}
查找右边界
相似地，我们也可以反向推得到右边界写法：
左闭右闭写法：
private int getRight(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] <= target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
if (r == -1 || nums[r] != target) {
return -1;
}
return r;
}
左开右闭写法：
private int getRight(int[] nums, int target) {
int l = 0;
int r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] <= target) {
l = mid + 1;
} else {
r = mid;
}
}
// 注意：因为这里是左闭右"开" 所以r指针指向的并不是实际的位置，r-1才是。
if (r == 0 || nums[r - 1] != target) {
return -1;
}
return r - 1;
}
查找插入位置
搜索插入位置实际上和查找左边界非常类似，如果能搜索到刚好等于target的mid，自然最好，搜索到的位置就是插入位置。
左闭右闭写法：
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] > target) {
r = mid - 1;
} else if (nums[mid] < target) {
l = mid + 1;
} else {
return mid;
}
}
return l;
}
左闭右开写法：
public int searchInsert(int[] nums, int target) {
int l = 0;
int r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > target) {
r = mid;
} else if (nums[mid] < target) {
l = mid + 1;
} else {
return mid;
}
}
return l;
}
中指针整型溢出问题
中指针溢出问题指的是在静态类型语言下，mid = (l + r) / 2可能会造成int溢出，本质上是l + r大小溢出。
在JDK下，该bug存在了9年之久。
一般有两种解决方案：
- 改写为先减再加的方式：
mid = l + (r - l) / 2。可以避免l + r溢出。 - 右移替代除法，效率会高一点点：
mid = l + ((r - l) >> 1)
特别的，在JDK中是这么写的：mid = (l + r) >>> 1。
>>>是无符号右移运算符，与>>的区别是不考虑符号位，总是往左侧补0。l + r溢出的时候最高符号位从0变成了1，而用>>>又变成了0，所以可以解决溢出问题。
但是用这种写法要保证l + r >= 0，如果l + r为负数，高位补0就会得到错误的正数。
在一般情况下，l与r代表下标，相加恒为正数，但部分题目的搜索的不是下标，而是数值。l与r可能代表的是数值，相加可能为0。
例如：LeetCode.462最小操作次数使数组元素相等II。