vlambda博客
学习文章列表

读完本文，你可以写对简单的二分查找题。

二分查找也称为折半查找、对数查找，思路很简单，对于要查找的目标值，不是通过从前往后迭代查找，而是每次查找中间位置，每次操作排除掉一半的数据。

二分查找比较容易出错，主要原因在于边界难以确定，而且二分查找的写法多样，多种方式容易弄混。

我们来看最简单的一道题，leetcode 704，题目如下：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

源代码：

class Solution {
public:
    int search(vector<int>& nums, int t) {
        int l=0, r=nums.size()-1;
        int ans = l;
        while(l<=r){
            int m = (l+r)/2;
            if(nums[m]>=t){
                ans = m;
                // left
                r = m-1;
            }else{
                l = m+1;
            }
        }
        return nums[ans] == t?ans:-1;
    }
};

这个解法是一个模板，代码看起来不多，让我们一行行的看。

函数输入的是一个有序数组和一个目标值t。

1 初始值

第一行我们定义二分查找的左右区间为l=0和r=数组最后一个下标。从l和r的定义可以看出，l和r都是有效位置。

第二行我们将ans设为l，这里设置成r也可以。ans只是一个临时位置，但是最好是有效的，因为最后一行会用这个取数组值。如果在整个二分查找过程中没有找到新的ans，那么ans就是初始值。

2 退出条件

接着是while循环，这里使用l>r作为退出条件，比较容易记忆，因为l大于r肯定是二分结束了，有些写法是l>=r结束二分，这种写法也可以，但是光从这一行的理解来说，不怎么直观，因为需要结合后面的代码才能满足这个条件，虽然只有几行代码，显然前者耦合性更小（不需要关心任何其他代码）。

3 二分

接下来进入循环， ，也就是二分，一般使用下界，也可以使用上界，影响不大。

4 check判断

下一行是if语句，if(nums[m] >= t)如果成功，则说明当前中间位置的值比较大，所以调整上边界r为m-1。因为m这个位置已经判断过了，所以从m-1位置开始继续下一轮。这里ans=m，为什么放在这里而不是放在下面调整l的边界时候呢？

因为这里是大于等于，当等于的时候，ans就会更新成新的值。

如果判断失败，则说明当前中间位置的值比较小，调整下边界l为m+1。

为什么易出错

这上面4步，每一步都可能走错，这也是为什么写对二分不是那么容易的事情。

特殊情况1：ans初始化超出数组边界的情况

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

输入：[1,3,5,6], 2

输出：1

源码：

class Solution {
public:
    int searchInsert(vector<int>& nums, int t) {
        int l=0, r=nums.size()-1;
        int ans = r+1;
        while(l<=r){
            int m = (l+r)/2;
            if(nums[m] >= t){
                ans = m;
                r = m-1;
            }else{
                l = m+1;
            }
        }
        return ans;
    }
};

这道题因为需要找到插入的位置，而这个位置可能刚好是最后一个元素的下一位，因此初始化ans为r+1，如果t大于所有元素，ans不能更新，就会返回r+1。

特殊情况2：二分收缩方向

在做了几个二分题目后，你会发现二分的套路都可以用上面一样的模板，但是要注意ans的初始值和收缩方向，什么是收缩方向，比如数组是[1, 2, 3, 5, 5, 7, 9, 10]，如果我们从左边开始收缩，也就是<=t的话，最终会收缩到第二个5那里，如果从右边（高位）收缩，也就是>=t为check判断，最终会收缩到第一个5那里，所以这是有区别的。如果没有重复元素，一般来说我们可以任意一边收缩。来看leetcode 34这道题，题目如下：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

输入：nums = [5,7,7,8,8,10], target = 8

输出：[3,4]

这道题就需要上面提到的收缩方向：

class Solution {
public:
    int lower(vector<int>& nums, int t){
        int l = 0, r = nums.size()-1;
        int ans = r;

        while(l<=r){
            int m = (l+r)/2;
            if(nums[m] >= t){
                ans = m;
                r = m-1;
            }else{
                // < t
                l = m+1;
            }
        }
        return nums[ans]==t?ans:-1;
    }
    int upper(vector<int>& nums, int t){
        int l = 0, r = nums.size()-1;
        int ans = 0;

        while(l<=r){
            int m = (l+r)/2;
            if(nums[m] > t){
                r = m-1;
            }else{
                // <= t
                ans = m;
                l = m+1;
            }
        }
        return nums[ans]==t?ans:-1;
    }
    vector<int> searchRange(vector<int>& nums, int t) {
        if(nums.empty()){
            return {-1, -1};
        }
        auto l = lower(nums, t), r = upper(nums, t);
        return {l, r};
    }
};

计算上和下2个方向，然后拼起来就可以了。

上面简单讲解了3个二分题目，最重要的还是要理解第一题里的四步，第二题是ans初始化的变化题，第三题是二分的收缩特性题。

总结

二分需要多做题多总结，本人做的二分题不多，后面还会继续写一些二分的深入分析。看起来很简单的思路，却非常容易让人掉坑，二分在软件开发过程中也会有很多应用，关键是性能好，值得熟练掌握。