二分查找及其应用

本贴最后更新于 449 天前,其中的信息可能已经事过境迁

概述

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

框架与说明

通用二分查找框架

框架处理过程:

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

代码框架如下:

int binarySearch(int [] nums,int target) {
    int left = 0, right = ...;
  
    while(...){
        //防止溢出等同于mid = (left +right)/2
        int mid = left + (right - left)/2; 
        if(nums[mid] == target) {
            ...
        }else if (nums[mid] < target) {
            left = ...
        }else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...
}

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

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

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

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

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

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

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

基本二分查找

image-20201028124753048

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

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

  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]**这两个区间中。后一种用法可能会在左边界查找右边界查找中会用到。

左边界查找

代码实现:

public int leftBound(int[] nums, int target) {
    // 细节1:right赋值为length,意味着搜索区间范围左闭右开
    int left = 0, right = nums.length;
    // 细节2
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // 细节3
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 细节4
            right = mid;
        }
    }
    // 细节5
    return nums[left] == target ? left : -1;
}

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

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

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

  1. 为何返回 left?

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

右边界查找

代码实现:

public int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            //细节1
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    //细节2
    return nums[left - 1] == target ? left - 1 : -1;
}

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

  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】

代码实现:

 public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    int min = nums[left];
    while (left <= right) {
      int mid = ((right - left) >> 1) + left;
      if (nums[mid] < min) {
        min = nums[mid];
      }
      if (nums[left] < nums[right]) {
        right = mid - 1;
      } else if (nums[left] > nums[right]) {
        // 证明最小值在mid的前面
        if (mid > left && nums[mid] > nums[mid - 1]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else if (nums[left] == nums[right]) {
        return min;
      }
    }
    return min;

总结

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

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3010 引用 • 8158 回帖 • 549 关注

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...