算法-二分查找的多种写法

二分查找

二分查找作为数组的基操,肯定是要牢牢掌握的,其思想十分简单,但是对于细节的处理,就可以看出你对二分算法的理解深刻与否。

如果没有真正的理解细节处的内涵,二分查找算法的编写就是玄学编写,这里加不加等号呢?这里是+1还是不变呢?最后该返回啥呢?

接下来我们就来看看这些细节该如何处理

下面使用三个二分查找使用的场景做出分析:寻找一个数寻找左侧边界寻找右侧边界

二分查找的骨架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = ..;// nums.length-1还是nums.length
int mid;
while(left..right){// <=还是<
mid = (left + right) >> 1;// (right - left) / 2 + left(left + right) >> 1还是 (right + left) / 2
if(nums[mid] == target){
.. = ..; // right还是left mid-1还是mid
}else if(target < nums[mid]){
right = ..; // mid-1还是mid
}else {
left = ..; // mid+1
}
}
return ..;// left或者要做什么处理
}

或许你经常看见一些代码不会将等于的情况单独列出来,但是我觉得对于二分查找的分析,将等于的情况单独分离出来,会更有利于理解

等到彻底理解后,随便怎么写都不会少搜索区间的时候,那就随便合并语句了

上述骨架中..出现的地方就是我们需要去琢磨的细节之处了,乍一看,全是细节,所以叫魔鬼细节探究

先解决最好解决的一个细节

很多人都在LeetCode官网中看到有时候官网对于中间值的取值

有时候会使用(right - left) / 2 + left

有时候会使用(left + right) >> 1

有时候看见别人写的代码中又是(right + left) / 2,肯定会很迷糊,这三者的计算到底有什么不同之处呢?

(right - left) / 2 + left这种写法是为了防止(left+right)因为数据过大导致溢出,导致mid计算错误,

(left + right) >> 1这是位运算,处理效率会高一点

(right + left) / 2这就是正常写法,一般也不会出错

接下来按照二分查找的常见使用场景来逐个做出分析

查找一个数

场景1:查找一个数,存在返回索引,不存在返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
// [left,right]
while(left <= right) {
mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}
else if (nums[mid] < target){
left = mid + 1;
}
else if (nums[mid] > target){
right = mid - 1;
}
}
return -1;
}
  1. 循环条件是left <= right而不是left < right

这里我们要说一下什么时候应该退出循环,就是当我所有的元素都搜索完成之后(即搜索区间里面没有元素的时候),或者是找到了目标值的时候可以直接终止,返回结果。

当right赋值为nums.length - 1,则搜索区间为[left,right],所有元素搜索完成的条件应该是left==right+1,即搜索区间为[right+1,right],符合要求。如果循环退出条件改为 left<right,则退出循环的时候,搜索区间为[left,right],会缺少搜索第left个元素,不符合要求

如果**right赋值为nums.length**,则搜索区间为[left,right),所有元素搜索完成的条件应该是left==right,即搜索区间为[left,right)

  1. nums[mid] > target的时候,为什么是right = mid - 1; 而不是right = mid;

还是回到搜索区间的问题上,当我发现当前这个元素与target不等而是大于target,那么我只需要搜索左边区间,即将[left,right]分割为左边区间[left,mid-1]和右边区间[mid+1,right],所以下一步应该将mid-1赋值给right

  1. 此算法的用途

这种方法只可以在找到目标值的情况下返回索引,但是当nums为[1,2,2,2,4]的时候,返回的值是2,没错,但是这样可能就无法满足我们的需求了,只能在数组是严格递增的情况下使用。

如果场景变为:查找一个数,如果找到则返回索引位置,如果找不到,则返回目标值插入数组的位置

这个时候其实只要最后返回left即可

返回左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
// [left,right]
while (left <= right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
  1. 为什么最后返回的时候要做出判断?

当目标元素比所有的值都小的时候,在最后一次循环的时候,right = mid - 1,left此时为0,但是无法确定该元素是否为目标元素,所以需要做出判断,

当目标元素比所有的值都大的时候,在最后一次循环的时候,left= mid + 1,left此时为数组长度,这时候则说明,该元素在此数组中不存在,也要做出判断

  1. 为什么找到的一定是左边界?

因为这一段代码

1
2
3
if(nums[mid] == target){
right= mid - 1;
}

当数组元素等于目标元素的时候,不着急返回,而是缩小查找范围。因为需要查找左边界,所以需要向左边收缩区间

  1. 这里面while的循环条件可以改为left < right吗?

当然可以,只要理解了搜索区间,只要能够保证所有的元素都被查找了,怎么写都可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
// 如果target毕nums所有的值都小,则right会变成-1,left就是0
// 如果target比nums所有的值都大,则left会变成nums.length,right就是nums.length-1
if (left == nums.length || nums[left] != target) {
return -1;
}
return left;
}

当目标元素比所有的值都大的时候,在最后一次循环的时候,left= mid + 1,left此时为数组长度,这时候则说明,该元素在此数组中不存在,需要单独做出判断

当目标元素比所有的值都小的时候,在最后一次循环的时候,right = mid ,left此时为0,但是无法确定该元素是否为目标元素,所以需要做出判断,

返回右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while(left <= right) {
mid = left + (right - left) / 2;
if(nums[mid] == target){
left = mid + 1;
}
else if (nums[mid] < target){
left = mid + 1;
}
else if (nums[mid] > target){
right = mid - 1;
}
}
// 如果target比nums中所有元素都大,left在nums.length,right在nums.length-1
// target比nums所有元素都小,left在0,right是-1
if (left == 0 || nums[left - 1] != target) {
return -1;
}
return left - 1;
}
  1. 为什么最后返回的时候要做出判断?

当目标元素比所有的值都大的时候,在最后一次循环的时候,left= mid + 1,left此时为数组长度,这时候则说明,该元素在此数组中不存在,也要做出判断

当目标元素比所有的值都小的时候,在最后一次循环的时候,right = mid - 1,left此时为0,但是无法确定该元素是否为目标元素,所以需要做出判断,

  1. 为什么找到的一定是右边界?

因为这一段代码

1
2
3
if(nums[mid] == target){
left = mid + 1;
}

当数组元素等于目标元素的时候,不着急返回,而是缩小查找范围。因为需要查找右边界,所以需要向右边收缩区间

  1. 如何修改循环条件为left < right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
// 当target比数组中所有元素都小的时候,right和left都走到了0的位置
// 这时候这说明,数组中不存在target元素,直接返回0
if (left == 0) {
return -1;
}
// 当target比数组所有元素都大的时候,right和left都走到了数组长度的位置,
// 如果数组最后一个元素不是这说明数组中没有target元素
if (nums[left - 1] != target) {
return -1;
}
return left - 1;
}
给作者买杯咖啡吧~~~