関小君刷题记

说起二分查找(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常见算法之二分查找超详细白话讲解/