X

LEETCODE常见算法之二分查找超详细白话讲解

说起二分查找(Binary Search),我想大家都不会陌生,该算法在理解上不存在任何难度,但在刷题过程中,即使很简单的二分查找题目,经常会花费大量时间来调试边界条件,因此,本篇文章我们着重总结一下所有二分查找的边界问题。

首先来看下常见的二分查找题型:

  1. 基础版本:查找数组中某个数值的下标。
  2. 查找第一个大于等于(小于等于)某个数的下标
  3. 查找第一个大于(小于)某个数的下标

接下来,我们逐一来分析。


一. 基础版本:查找数组中某个数值的下标。

这种类型的二分查找是最为简单的,通常用于判断一个已排序好的数组中是否存在某个target数值问题。模板如下:

public int binarySearch(int[] a, int target) {
 int low = 0;
 int high = a.length - 1;
 int mid = 0;
 while (low <= high) {
  mid = (low + high) / 2;
  if (target == a[mid]) {
   return mid;
  } else if (target < a[mid]) {
   high = mid - 1;
  } else {
   low = mid + 1;
  }
 }
 return -1;
}

这是最为基础的一种写法,当mid值等于target时,直接返回mid。当mid小于target时,我们要增加区间内的取值,因此,令low等于mid加一,反之令high等于mid减一。


二. 查找第一个大于等于某个数的下标

这个查找就变得稍微复杂一些。因为大于等于target的数值可能存在多个,这时我们必须找到第一个大于等于target的数值。相应的,代码会做出两处改变:

public int firstGreatOrEqual(int[] a, int target) {
 int low = 0;
 int high = a.length - 1;
 int mid = 0;
 while (low <= high) {
  mid = (low + high) / 2;
                // 这里大于和等于属于同一种情况
  if (a[mid] >= target) {
   high = mid - 1;
  } else {
   low = mid + 1;
  }
 }
        // 返回值要做越界判断
 return low < a.length ? low : -1;
}

原则上,当mid大于等于target时,我们向左半区继续查找,反之向右半区查找。因为是求解大于等于target的数值,因此区间下限low是可能的返回结果。

二分查找的终止条件是当low大于high的时刻,因此终止前最后一步的状态一定是low与high两个指针重合的时刻,此时,mid实际上等于low,也等于high。如果mid指向的数值大于等于target时,high会减一,而low不变,此时low就是最终结果。反之,如果mid指向的数值小于target时,high不变,low会加一,理论上low应该是返回结果,但是low在加一操作后可能会出现越界,因此,当越界时,说明没有找到target值,这时应该返回-1.


三. 查找第一个小于等于某个数的下标

这与第二种二分查找的思路没有任何区别,你能尝试着自己写出来吗?看下代码:

public int firstSmallOrEqual(int[] a, int target) {
 int low = 0;
 int high = a.length - 1;
 int mid = 0;
 while (low <= high) {
  mid = (low + high) / 2;
  if (a[mid] <= target) {
   low = mid + 1;
  } else {
   high = mid - 1;
  }
 }
 return high >=0 ? high : -1;
}

我们求解的是小于等于某个数的下标 ,因此你要明确知道最终的high值是可能的返回结果。本题,小于与等于两个条件属于同一种情况,而最后的返回值high,要看他的坐标是否大于等于0,如果是,返回high,否则,说明数组中所有数字均大于target,返回-1。


四. 查找第一个大于某个数的下标

有了上面的基础,再看到这里,你应该会很快想出逻辑了吧?其实不难发现,我们要做的就是如何给大于,小于和等于三个条件分组,本题是求第一个大于某个数的下标,因此大于是一种分支,而小于和等于属于另一个分支:

public int firstGreat(int[] a, int target) {
 int low = 0;
 int high = a.length - 1;
 int mid = 0;
 while (low <= high) {
  mid = (low + high) / 2;
  if (a[mid] > target) {
   high = mid - 1;
  } else {
   low = mid + 1;
  }
 }
 return low < a.length ? low : -1;
}

五. 查找第一个小于某个数的下标

不再废话,直接上代码:

public int firstSmall(int[] a, int target) {
 int low = 0;
 int high = a.length - 1;
 int mid = 0;
 while (low <= high) {
  mid = (low + high) / 2;
  if (a[mid] < target) {
   low = mid + 1;
  } else {
   high = mid - 1;
  }
 }
 return high >=0 ? high : -1;
}

阶段总结:

我们不难发现,当列举出所有的二分查找场景之后,边界条件的判断变得清晰明确。我们总结一下:

  1. 无论什么情况下,二分查找的循环条件都是low<=high
  2. 当mid指向的值大于或者大于等于target时,我们需要减小mid,二分区间应变为low到mid-1,反之,二分区间变为mid+1到high。
  3. 当求某个特定值target的位置时,判断条件存在大于,等于,小于三个分支。若求大于等于某个target,或者小于某个target时,大于和等于属于一个分支,小于属于另一个分支。若求小于等于某个target,或者大于某个target时,小于和等于属于一个分支,而大于属于另一个分支。
  4. 当求某个特定值target的位置时,mid是最终解。当求大于或者大于等于target时,low是最终解,求小于或者小于等于target时,high是最终解。另外注意high与low超出数组边界时,代表没有找到符合条件的元素。

如果你对以上的总结仍然感到难以理解,你需要使用debug功能去一点一点的理解它的精髓。或者你可以直接记住上述逻辑,方便在编程时使用。


二分查找在Leetcode解题时的实际应用

当遇到题目时,如果你能够快速反应出该题的解题方式是二分查找的话,那么你将发现题目毫无难度。而关键问题在于很多题目你可能一上来无法想到要使用二分来解题。我们来看一道例题:

LEETCODE 69. Sqrt(x)

x 的平方根

实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

这就是一道经典的二分查找算法的使用场景。我们发现,题目不会明确的告诉你,要在一个递增数组中查找大于或者小于某个target的值,这需要我们自己来分析得出。如果将本题翻译成为二分查找思想的话,我们可以理解为,题目求的是,在1到x之间,找到一个数字n,保证n的平方是第一个小于等于x的数字。这样一来,你是否想到解法了呢?看下代码:

public int mySqrt(int x) {
    if(x<=1) return x;
    long low=1,high=x;
    while(low<=high){
        long mid=(low+high)/2;
        long n=mid*mid;
        if(n<=x){
            low=mid+1;
        }else{
            high=mid-1;
        }
    }
    return high>=0?(int)high:-1;
}

上述代码就是标准的第三类二分查找题型。

我们再举一个复杂一些的例子,比如我们给定了一个升序排序好的数组arr,求其中某个数字出现的次数。

这道题目要使用到多种二分查找的组合来解题。

  1. 首先我们使用第一类二分方法,返回数组中等于target值的任意下标,如果返回值为-1,说明数组中不存该值。否则数组中存在target。
  2. 找到第一个大于等于target的下标start。
  3. 找到第一个小于等于target的下标end。
  4. start到end区间即是target所在的范围。

总结:

本篇文章,我们重点分析总结了二分查找的边界问题,希望对你今后的解题能够提供帮助。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode常见算法之二分查找超详细白话讲解/
Categories: leetcode
kwantong:

View Comments (2)