【算法】二分查找——BinarySearch

一、概述

二分查找又称折半查找，是一种能够大幅减少时间复杂度的查找方法，但是二分查找要求线性表必须词用顺序储存结构，而且表中元素按关键字有序排列。

在后续讨论中，我们假设有序表递增有序。

二分查找中使用的术语：

目标 Target —— 你要查找的值 索引 Index —— 你要查找的当前位置 左、右指示符 Left，Right —— 我们用来维持查找空间的指标 中间指示符 Mid —— 我们用来应用条件来确定我们应该向左查找还是向右查找的索引。

二、一个典型的二分查找

二分查找的过程为：

从表的中间记录middle开始，如果要查找的目标值target等于middle，则查找成功；如果target>middle，则说明应从middle的右侧寻找target，将left的值更改为middle+1；反之则从middle的左侧寻找，将right的值更改为middle-1。重复操作直至查找成功，或者当查找区间为空时查找失败。

C++代码如下：

class Solution {
public:
  int Binary_Search(vector<int>& nums, int target) {
    int left=0;
    int right=nums.size()-1;
    while(left<=right)//应注意这里是left<=right而不是left<right，因为查找区间还有最后一个节点，需要进一步比较。
     {
      int middle=left+(right-left)/2;//相当于(right+left)/2，这么写是为了防止溢出
      if(nums[middle]<target){
        left=middle+1;
       }
      else if(nums[middle]>target){
        right=middle-1;
       }
      else {
        return middle;
       }
     }
    return -1;
   }

时间复杂度为\O(log_2n)，空间复杂度为\O(1)。

我在学校学习数据结构与算法，就只是勉勉强强学到这里了。下面是我的假期重开内容。

三、习题与胡乱分析

题单来源主要是这本书：二分查找 – LeetBook – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

它将二分查找与相关习题总结概括成了三种代码模板，对小白入门很友好。但是我只看出来它们只有几个条件不一样，并没有参悟其中玄机x

有没有看懂了的dl浇浇我x

1. 猜数字

习题链接：374. 猜数字大小 – 力扣（LeetCode） (leetcode-cn.com)

​

猜数字游戏的规则如下：

• 每轮游戏，我都会从1到n随机选择一个数字。 请你猜选出的是哪个数字。
• 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口int guess(int num)来获取猜测结果，返回值一共有 3 种可能的情况（-1，1或0）：

• -1：我选出的数字比你猜的数字小pick < num
• 1：我选出的数字比你猜的数字大pick > num
• 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。

示例 1：

​​

输入：n = 10, pick = 6输出：6

示例 2：

​

输入：n = 1, pick = 1输出：1

​

示例 3：

​

输入：n = 2, pick = 1输出：1

​示例 4：​

输入：n = 2, pick = 2输出：2

提示：

• 1 <= n <= 231- 1
• 1 <= pick <= n

典型的二分查找，比较简单，代码如下：

class Solution {
public:
  int guessNumber(int n) {
    int left=1;
    int right=n;
    int middle=1;
    while(left<=right){
      middle=left+(right-left)/2;
      if(guess(middle)==1){left=middle+1;}
      else if(guess(middle)==-1){right=middle-1;}
      else if(guess(middle)==0){return middle;}
     }
    return middle;
   }
};

2. Sqrt(x)

习题链接：69. Sqrt(x) – 力扣（LeetCode） (leetcode-cn.com)​

给你一个非负整数x，计算并返回x的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去 。

​

注意：不允许使用任何内置指数函数和算符，例如pow(x, 0.5)或者x ** 0.5。

​​

示例 1：

输入：x = 4  输出：2  

示例 2：

输入：x = 8  输出：2  解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 231- 1

按照典型的二分查找来寻找最相近的根即可。但是要注意不能使用middle*middle>x或者与之类似的方式判断middle的大小，因为当数据较大时，这种写法会导致溢出。因此采用x/middle>middle或与之类似的方式进行比较。

（不过官方解答竟然是用long long的方式解决了溢出问题……）

结束循环时返回的不是middle，这里我一开始没想到。不过具体返回的是哪一个值还是要看前面代码的。

解答如下：

class Solution {
public:
  int mySqrt(int x) {
    int left=1;
    int right=x;
    while(left<=right){
      int middle=left+(right-middle)/2;
      if(x/middle>middle){left=middle+1;}
      else if(x/middle<middle){right=middle-1;}
      else {return middle;}
     }
    return right;
   }
};

我这里返回的是right。以输入为8为例，最后一次循环开始时，left与right都为3，循环依然可以进行。执行操作后，right=2而left=3，此时方才退出循环。

看题解，发现每个人的做法都不尽相同，常见的有下面这些区别

• 首先判断特殊值

• 循环条件不是while(left<=right)，而是while(left<right)。

• 并不是left=middle+1，而是left=middle，最后return left

对模板各个部分不同的修改导致了整体的不同。（个人胡乱理解）

3. 停顿一下

在写这篇总结时，我突然想到，怎么样才能更快地写出一个正确的二分查找呢？有没有什么分析方法？

于是我参考了这篇博客：如何写出正确的二分查找？——利用循环不变式理解二分查找及其变体的正确性以及构造方式 – 五岳 – 博客园 (cnblogs.com)

然后我找到了《计算机算法设计分析习题解答》中的习题2-2，可能参悟了这七个算法就能掌握写出正确二分查找的精髓了吧。

于是这里留一个小尾巴~

4. 第一个错误的版本

习题链接：278. 第一个错误的版本 – 力扣（LeetCode） (leetcode-cn.com)

​

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有n个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4输出：4解释：调用 isBadVersion(3) -> false 调用 isBadVersion(5)-> true 调用 isBadVersion(4)-> true所以，4 是第一个错误的版本。

​

示例 2：

输入：n = 1, bad = 1输出：1

​

提示：

​

• 1 <= bad <= n <= 231- 1

要注意修改循环、左右区间更改条件等。

第一次把分号放在括号外面提交好几次……最后对着题解写艰难过了。

第二次很快就写出来了，主要是考虑清楚条件防止死循环。

代码如下：

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
​
class Solution {
public:
  int firstBadVersion(int n) {
    int left=1,right=n;
    while(left<right){//不能是<=，会死循环
      int middle=left+(right-left)/2;
      if(isBadVersion(middle)){right=middle;}
      else{left=middle+1;}
     }
    return right;
   }
};

5. 寻找峰值

习题链接：162. 寻找峰值 – 力扣（LeetCode） (leetcode-cn.com)

​

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设nums[-1] = nums[n] = -∞。

你必须实现时间复杂度为O(log n)的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,4]

输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。

示例2：

输入：nums = [1,2,1,3,5,6,4]

输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2；  或者返回索引 5， 其峰值元素为 6。

提示：

• 1 <= nums.length <= 1000
• -231<= nums[i] <= 231- 1
• 对于所有有效的i都有nums[i] != nums[i + 1]

根据罗尔中值定理，要判断是否为峰值应当看这个位置导数是否为0。那么在这道题中，如果一个数比右边位置的数大，就应该在左侧区间内继续查找，反之则在右边位置查找（但是不能同时和左右两边的数字比较，不然就会陷入不知道查找哪一边区间的尴尬境地）。

另外这道题还有一点不严谨，那就是没有明确数组两端点是否可以为峰值。根据测试用例，可以猜测出题人是认为两端点可以作为峰值的。

代码如下：

class Solution {
public:
  int findPeakElement(vector<int>& nums) {
    int n=nums.size();
    if(n==1||nums[0]>nums[1]){
      return 0;
     }
    if(nums[n-1]>nums[n-2]){
      return n-1;
     }
    //排除几种特殊情况。
    int left=-1,right=n;
    while(left+1!=right){
      int middle=left+(right-left)/2;
      if(nums[middle]>nums[middle+1]){
        right=middle;
       }
      else left=middle;
     }
    return right;
   }
};

6. 找到K个最接近的元素

习题链接：658. 找到 K 个最接近的元素 – 力扣（LeetCode） (leetcode-cn.com)

​

给定一个排序好的数组arr，两个整数k和x，从数组中找到最靠近x（两数之差最小）的k个数。返回的结果必须要是按升序排好的。

​

整数a比整数b更接近x需要满足：

• |a - x| < |b - x|或者
• |a - x| == |b - x|且a < b

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3输出：[1,2,3,4]

示例 2：

输入：arr = [1,2,3,4,5], k = 4, x = -1输出：[1,2,3,4]

提示：

• 1 <= k <= arr.length
• 1 <= arr.length<= 104
• 数组里的每个元素与x的绝对值不超过104

​

其实这道题最简单最高效的方法是滑动窗口法，这个方法在之后会总结成专题（或许吧（咕咕咕））

也可以采用二分法来解题。

代码如下：

class Solution {
public:
  vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left=0,right=arr.size()-k;
    while(left<right){
      int middle=left+(right-left)/2;
      if((x-arr[middle])>(arr[middle+k]-x)){//右边比左边更适合，所以选择右区间。
        left=middle+1;
         }
      else{right=middle;}
     }
    return vector<int>(arr.begin()+left,arr.begin()+left+k);
   }
};

留一个尾巴在这里~

四、小结

• 使用二分法解题可以使时间复杂度降至O(log_2n)，可以完成一些算法的要求。

• 使用二分法拥有一个大概的框架，但是每一步具体的条件内容随着具体题目的要求而改变。

五、参考资料

1. 如何写出正确的二分查找？——利用循环不变式理解二分查找及其变体的正确性以及构造方式 – 五岳 – 博客园 (cnblogs.com)

2. 二分查找 – LeetBook – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

3. 《计算机算法设计与分析习题解答》第5版（王晓东）