二分查找思路及模板_二分查找模板

二分查找的思路

对于一个有序数组，如果我们想查找指定数值的索引，最朴素的方法就是从头到尾依次遍历，但是这样的时间复杂度是 O(n)，相对而言，还有更快的方法。而二分查找就是其中之一。

二分查找简单理解，我们先看一看数组中间的数值mid和我们要查到的数值做一个比较，如果比我们要查找的数值大，那么我们要找的数值肯定在中间数值的左边，否则在右边。这样一来，只要查询一次，就可以抛弃掉一半不符合条件的数值。通过这样的方式，每次都能缩小一半的范围，这样我们就能查询相当少的次数来找到我们要找的数值。这种方法被称为二分查找

二分查找的模板

模板一：找满足条件的最左侧的值

模板代码：

        int l=0,r=nums.length-1;
        while(l<r){
            int mid =l+r >> 1;
            if(nums[mid]>=target){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        return l;
1
2
3
4
5
6
7
8
9
10

模板二：找满足条件的最右侧的值

模板代码：

        int l=0,r=nums.length-1;
        while(l<r){
            int mid =l+r+1 >> 1;
            if(nums[mid]<=target){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
1
2
3
4
5
6
7
8
9
10

模板中 l=0,是最左边的元素，数组索引都是从0开始，所以写的是l=0，如果最左边不是0，那么改成对应的数即可。r=nums.length-1 是找最左边的元素，与左边的同理。

对比可以发现，两个模板的区别就是mid不同，满足的if条件不同之后，left 和 right赋值不同。如果你在写的时候，mid取值你不知道需不需要+1，你可以看你写的if else中 如果是r=mid-1;那么mid就+1，如果是l=mid+1; 那么mid就不加1。

这两个模板，其实选择满足if的条件是模板的精髓，首先这个题一定要满足二段性质，什么意思呢？ 就是这个数组一定一定要满足一个性质，使它可以分成两段。并且其中一段是满足条件，一段不满足条件，如果性质找错了，那就不可能算对了。这样说比较抽象，下面通过举例说明

下面通过三个例子带你感受模板的微妙

LeetCode 704题

直达力扣官网查看
https://leetcode.cn/problems/binary-search/

咱们先假设目标值一定存在，那么就一定会存在，目标值右边的数大于它，目标值左边的数小于它。这个就是二段性的性质，然后我们就可以把满足条件写入if的判断语句中。

对于这道题，刚才我们所说的性质可以是nums[mid]>=target 也可以是nums[mid]<=target，当然选择不同的条件，我们使用的模板也不同。
下面我选择nums[mid]>=target ，那么我们就是找满足条件的最左侧的值，所以就可以套第一个模板，因为如果没有找到需要返回-1；所以在最后加一个判断就可以了。

class Solution {
    public int search(int[] nums, int target) {


        int l=0,r=nums.length-1;
        while(l<r){
            int mid =l+r >> 1;

            if(nums[mid]>=target){
                r=mid;
            }else{
                l=mid+1;
            }

        }

        if(nums[l]!=target){
            l=-1;
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

再来看LeetCode 852题

直达力扣官网查看
https://leetcode.cn/problems/peak-index-in-a-mountain-array/

这道题，我们根据题目的要求可以知道：我们要找的索引i，必定满足 arr[i]>arr[i-1]。当然也满足arr[i]>arr[i+1]。这就是我们的二段性性质。数组中肯定有一段是满足我们的性质，另一段不满足我们的性质。现在我以 必定满足 arr[i]>arr[i-1]举例。
所以我们是要找满足条件的最右边的值：套二个模板

        int l=0,r=nums.length-1;
        while(l<r){
            int mid =l+r+1 >> 1;
            if(arr[mid ]>arr[mid -1]){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
1
2
3
4
5
6
7
8
9
10

再来看LeetCode 69题

直达力扣官网查看
https://leetcode.cn/problems/sqrtx/
可以先想一下这道题需要满足的性质是什么，然后再往下看

分析：根据题目要求，我们要找x的算术平方根，x的算术平方根肯定是在0到x之间，所以我们其实就是在0-x之前找一个数，但是我们要找x的算术平方根，结果只保留整数部分，其实就是向下取整。
所以这道题满足 midmid<=x 其中mid是x的算术平方根
解释：因为要找x的算术平方根，如果不向下取整，那么 结果就是midmid=x。 而现在mid向下取整了，如果x的算术平方根不是整数，那就肯定会小于x。
如：8的算术平方根是2.82842… 向下取整就是2。所以2*2肯定是小于8的

根据性质mid*mid<=x。我们要找的是最满足条件最右侧值。所以还是套用第二个模板

注意：题目中最大数是x，所以要把r=nums.length-1改成r=x
题目提示 x的范围是0——2的31次方-1，所以mid*mid 会出现溢出，所以改成mid<=x/mid

class Solution {
    public int mySqrt(int x) {
        int l=0,r=x;
        while(l<r){
            int mid =l+r+1 >> 1;
            if(mid<=x/mid){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结

当我们拿到一个题目时，首先判断这个题是否符合二段性质，如果符合，那么我们只需要找到这个性质，然后套用模板即可；