二分查找细节讨论
二分查找框架
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
public int binarySearch (int[] nums, int target) {
int left = 0;
int rigt = ...;
while (left ... rigt) {
int mid = (left + rigt) / 2;
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
left = ...;
}else if (nums[mid] > target) {
rigt = ...;
}
}
return -1;
}
…代表需考虑的细节位置,如:while循环中的不等号是否应该带等号,left是否应该加一,right是否应该减一等。
所有算法都有一点需注意:计算 mid 时需要技巧防止溢出同时加快运算速度,
建议写成: mid = start + ((end - start) >> 1)
寻找一个数(有序数组 nums = [1,2,2,2,3],target = 2,此算法返回的索引是 2)
场景描述:即搜索一个数,如果存在,返回其索引,否则返回 -1。
public int binarySearch (int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = start + ((end - start) >> 1);
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
上述代码中:为什么 while 循环的条件中是 <=,而不是 < ?
因为初始化 right 的赋值是 nums.length - 1,即最后一个元素的索引,而不是 nums.length。
while(left <= right)的终止条件是 left == right + 1,写成区间的形式就是 [right + 1, right],或者带个具体的数字进去 [3, 2],可见这时候搜索区间为空,因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的,直接返回 -1 即可。
while(left < right)的终止条件是 left == right,写成区间的形式就是 [right, right],或者带个具体的数字进去 [2, 2],这时候搜索区间非空,还有一个数 2,但此时 while 循环终止了。也就是说,索引 2 没有被搜索,如果这时候直接返回 -1 就可能出现错误。
非要用 while(left < right) 也可以,只需加上以下代码:
//...
while(left < right) {
// ...
}
//最后加一个遗漏检查
return nums[left] == target ? left : -1;
寻找左侧边界的二分搜索(有序数组 nums = [1,2,2,2,3],target = 2,此算法返回的索引是 1)
场景描述:即搜索一个数,如果存在,返回其左边界索引,否则返回 -1。
public int binarySearch (int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left;
}
上述代码中:为什么 while(left < right) 而不是 <= ?
因为初始化 right = nums.length 而不是 nums.length - 1 。因此每次循环的是 [left, right) 左闭右开。while(left < right) 终止的条件是 left == right,此时搜索区间 [left, left) 恰巧为空,所以可以正确终止。
为什么没有返回 -1 的操作?如果 nums 中不存在 target 这个值,怎么办?
函数的返回值(即 left 变量的值)取值区间是闭区间 [0, nums.length],所以我们简单添加两行代码就能在正确的时候 return -1。
while (left < right) {
//...
}
//跳出left值只能为0 或者 nums.length
// target 比所有数都大,即 nums.length
if (left == nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] == target ? left : -1;
为什么该算法能够搜索左侧边界?
找到 target 时不要立即返回,而是缩小区间右边界 right,在区间 [left, mid) 中继续搜索,即不断向左收缩,达到锁定左侧边界的目的。
很重要:!!! 可以看到当mid为target或者大于target的操作,其实是一样的,都是right=mid,
所以最后返回的left,其实是数组中,大于等于target的元素的第一个位置。
寻找右侧边界的二分搜索(有序数组 nums = [1,2,2,2,3],target = 2,此算法返回的索引是 3)
场景描述:即搜索一个数,如果存在,返回其右边界索引,否则返回 -1。
public int binarySearch (int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1;
}
如果 nums 中不存在 target 这个值,怎么办?
**while 循环结束时,nums[left] 一定不等于 target 了,而 nums[left - 1]可能是target。**类似前面的左侧边界搜索,因为 while 的终止条件是 left == right,就是说 left 的取值范围是 [0, nums.length],所以可以添加两行代码,正确地返回 -1。
while (left < right) {
// ...
}
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
最后总结
寻找具体的数 | 寻找数的左侧边界 | 寻找数的右侧边界 | |
---|---|---|---|
初始条件 | right = nums.length - 1 | right = nums.length | right = nums.length |
搜索区间 | [left, right] | [left, right) | [left, right) |
while的条件 | while (left <= right) | while (left < right) | while (left < right) |
left的处理 | mid+1 | mid+1 | mid+1 |
right处理 | mid-1 | mid | mid |
nums[mid] == target | 立即返回索引 | right = mid | left = mid + 1 |
遗漏处理方法 | 无 | if (left == nums.length) return -1;return nums[left] == target ? left : -1; | if (left == 0) return -1; return nums[left-1] == target ? (left-1) : -1; |