vcjmhg 的个人博客

自律者自由

  menu
80 文章
13419 浏览
2 当前访客
ღゝ◡╹)ノ❤️

二分查找及其应用

概述

二分查找算法是一种效率极高的算法,也是为数不多时间复杂度在 O(logn) 量级的算法。算法思想并不难理解,但是某些细节却十分复杂,因而本文尝试从一个通用框架入手,通过对不同细节的填补,生成在三种情况下适用的不同框架。同时后边给了一些二分查找的里边,便于读者练习。

框架与说明

通用二分查找框架

框架处理过程:

11. 初始化:为left和right赋值
22. 循环退出条件
33. 比较中值和目标值关系,分情况处理
4	1. 相等
5	2. 小于
6	3. 大于

代码框架如下:

 1int binarySearch(int [] nums,int target) {
 2    int left = 0, right = ...;
 3  
 4    while(...){
 5        //防止溢出等同于mid = (left +right)/2
 6        int mid = left + (right - left)/2; 
 7        if(nums[mid] == target) {
 8            ...
 9        }else if (nums[mid] < target) {
10            left = ...
11        }else if (nums[mid] > target) {
12            right = ...
13        }
14    }
15    return ...
16}

分析上边的框架,可能有两个奇怪的地方:

第一个是 mid 的计算方法比较奇怪

第二个整个 if 判断过程中没有 else分支

其实这两个问题也是二分查找的两个重要点。

针对第一点 mid 如果使用传统的写法 mid = (left + right)/2 确实比较容易理解,但 left 和 right 直接相加可能会导致上溢出的风险,因而需要使用 mid = left + (right - left)/2

第二个问题可能更多是一个技巧,因为二分查找思想可能很容易理解,但是细节却比较难以捉摸,因而在使用二分查找时要把所有情况用 else if 写清楚,而不要出现 else,这样可以清晰的展现出所有分支的细节,便于理解和排错。

同时,在整个模板中,我们可以看到有好多省略号 ... 标记,这个是容易出现细节问题的地方,也是我们在使用二分查找需要尤为注意的问题,后边会结合一些简单实例,来说明一下这些细节会有那些变化。

基本二分查找

image-20201028124753048

 1public int binarySearch(int[] nums, int target) {
 2    // 初始化,细节一:right此处复制为nums.length - 1,
 3    //相当于搜索区间为[left,righty]
 4    int left = 0, right = nums.length - 1;
 5    // 循环退出条件,细节二:由于细节一的原因,此处要使用left<=right
 6    //,从而保证能够搜索到right的位置
 7    while (left <= right) {
 8      // 计算中值
 9      int mid = left + (right - left) / 2;
10      // 查找到目标结果直接返回对应索引的位置
11      if (nums[mid] == target) {
12        return mid;
13      } else if (nums[mid] < target) {
14        // 细节三:因为已经验证过mid位置,因此需要从[mid+1,right]区间开始查找
15        left = mid + 1;
16      } else if (nums[mid] > target) {
17        // 细节四:原因同细节三
18        right = mid - 1;
19      }
20    }
21    // 区间内所有值都已搜索完毕,直接返回-1
22    return -1;
23  }

基于初始模板,我们可以很快写出基本的二分查找算法,但是针对实现过程中的一些细节,我们需要做一些说明:

  1. 为什么 while 循环的条件中是 <=,而不是 < ?

首先由于我们初始化的时候选择的右边界就是 right = nums.length -1,也即右边界是可以被访问到的,所以我们在终止条件判断的时候需要加上这个等号,搜寻的时候,搜索区间为**[left,right]**一个闭区间。

这二者可能出现在不同功能的二分查找中,区别是:前者相当于两端都闭区间 [left, right],后者相当于左闭右开区间 [left, right),因为索引大小为 nums.length 是越界的。

  1. 为什么 left = mid + 1,right = mid - 1?我看有的代码是 right = mid 或者 left = mid,没有这些加加减减,到底怎么回事,怎么判断?

这个也是二分查找的重要细节,刚才我们说了此处的搜索区间是[left,right],因此当判断 mid 之后,我们需要将搜索区间锁定在**[left,mid-1]、[mid+1,right]**这两个区间中。后一种用法可能会在左边界查找右边界查找中会用到。

左边界查找

代码实现:

 1public int leftBound(int[] nums, int target) {
 2    // 细节1:right赋值为length,意味着搜索区间范围左闭右开
 3    int left = 0, right = nums.length;
 4    // 细节2
 5    while (left < right) {
 6        int mid = left + (right - left) / 2;
 7        if (nums[mid] == target) {
 8            // 细节3
 9            right = mid;
10        } else if (nums[mid] < target) {
11            left = mid + 1;
12        } else if (nums[mid] > target) {
13            // 细节4
14            right = mid;
15        }
16    }
17    // 细节5
18    return nums[left] == target ? left : -1;
19}

左边界查找较之与基本二分查找多了几个细节点不同。

  1. 为什么 while(left < right) 而不是 <= ?

答:用相同的方法分析,因为 right = nums.length 而不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。while(left < right) 终止的条件是 left == right,此时搜索区间 [left, left) 为空,
所以可以正确终止。

  1. 为何返回 left?

答:因为搜索退出时一定是 left==right 因此即使返回的是 right 也影响不大。

右边界查找

代码实现:

 1public int rightBound(int[] nums, int target) {
 2    int left = 0, right = nums.length;
 3    while (left < right) {
 4        int mid = left + (right - left) / 2;
 5        if (nums[mid] == target) {
 6            //细节1
 7            left = mid + 1;
 8        } else if (nums[mid] < target) {
 9            left = mid + 1;
10        } else if (nums[mid] > target) {
11            right = mid;
12        }
13    }
14    //细节2
15    return nums[left - 1] == target ? left - 1 : -1;
16}

这个相比左边界查找可能有两个细节地方改变:

  1. 中点值和目标值相同时,不直接返回而是要通过 left = mid + 1 将查找区间向右逼近,进而才能查找最右侧的值
  2. 返回值是 left -1 ,主要是因为,在找到目标值之后做了一个 left = mid +1 操作,从而实际我们想要的 mid 的值为 left -1。

典型例题

1. 寻找旋转排序数组中的最小值

image-20201028191109284

基本思路:

在二分查找的过程中比较最左侧和最右侧值的大小,如果右侧小,则搜索【mid+1,right】区间,同时要注意一种情况,就是 mid 隔开了最小值,因此需要判断 mid 位置元素是否是最小的元素,如果不是将搜索区间改成【left,mid-1】。 如果左侧小则直接搜索【left,mid-1】

代码实现:

 1 public int findMin(int[] nums) {
 2    int left = 0, right = nums.length - 1;
 3    int min = nums[left];
 4    while (left <= right) {
 5      int mid = ((right - left) >> 1) + left;
 6      if (nums[mid] < min) {
 7        min = nums[mid];
 8      }
 9      if (nums[left] < nums[right]) {
10        right = mid - 1;
11      } else if (nums[left] > nums[right]) {
12        // 证明最小值在mid的前面
13        if (mid > left && nums[mid] > nums[mid - 1]) {
14          right = mid - 1;
15        } else {
16          left = mid + 1;
17        }
18      } else if (nums[left] == nums[right]) {
19        return min;
20      }
21    }
22    return min;

总结

通过对上边三种二分查找框架的掌握,大部分二分查找问题都可以解决,还是那句话,二分查找本身思想比较简单,但是细节很折磨人,但是针对某个问题,逐个分析其细节,最后大部分问题应该还是可以比较好的解决的。


标题:二分查找及其应用
作者:vcjmhg
地址:https://vcjmhg.top/binary-search