二分查找的思路

對于一個有序數(shù)組，如果我們想查找指定數(shù)值的索引，最樸素的方法就是從頭到尾依次遍歷，但是這樣的時間復(fù)雜度是 O(n)，相對而言，還有更快的方法。而二分查找就是其中之一。

二分查找簡單理解，我們先看一看數(shù)組中間的數(shù)值mid和我們要查到的數(shù)值做一個比較，如果比我們要查找的數(shù)值大，那么我們要找的數(shù)值肯定在中間數(shù)值的左邊，否則在右邊。這樣一來，只要查詢一次，就可以拋棄掉一半不符合條件的數(shù)值。通過這樣的方式，每次都能縮小一半的范圍，這樣我們就能查詢相當(dāng)少的次數(shù)來找到我們要找的數(shù)值。這種方法被稱為二分查找

二分查找的模板

模板一：找滿足條件的最左側(cè)的值

模板代碼：

        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;

模板二：找滿足條件的最右側(cè)的值

模板代碼：

        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;

模板中 l=0,是最左邊的元素，數(shù)組索引都是從0開始，所以寫的是l=0，如果最左邊不是0，那么改成對應(yīng)的數(shù)即可。r=nums.length-1 是找最左邊的元素，與左邊的同理。

對比可以發(fā)現(xiàn)，兩個模板的區(qū)別就是mid不同，滿足的if條件不同之后，left 和 right賦值不同。如果你在寫的時候，mid取值你不知道需不需要+1，你可以看你寫的if else中 如果是r=mid-1;那么mid就+1，如果是l=mid+1; 那么mid就不加1。

這兩個模板，其實(shí)選擇滿足if的條件是模板的精髓，首先這個題一定要滿足二段性質(zhì)，什么意思呢？ 就是這個數(shù)組一定一定要滿足一個性質(zhì)，使它可以分成兩段。并且其中一段是滿足條件，一段不滿足條件，如果性質(zhì)找錯了，那就不可能算對了。這樣說比較抽象，下面通過舉例說明

下面通過三個例子帶你感受模板的微妙

LeetCode 704題

直達(dá)力扣官網(wǎng)查看
https://leetcode.cn/problems/binary-search/

咱們先假設(shè)目標(biāo)值一定存在，那么就一定會存在，目標(biāo)值右邊的數(shù)大于它，目標(biāo)值左邊的數(shù)小于它。這個就是二段性的性質(zhì)，然后我們就可以把滿足條件寫入if的判斷語句中。

對于這道題，剛才我們所說的性質(zhì)可以是nums[mid]>=target 也可以是nums[mid]<=target，當(dāng)然選擇不同的條件，我們使用的模板也不同。
下面我選擇nums[mid]>=target ，那么我們就是找滿足條件的最左側(cè)的值，所以就可以套第一個模板，因?yàn)槿绻麤]有找到需要返回-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;
    }
}

再來看LeetCode 852題

直達(dá)力扣官網(wǎng)查看
https://leetcode.cn/problems/peak-index-in-a-mountain-array/

這道題，我們根據(jù)題目的要求可以知道：我們要找的索引i，必定滿足 arr[i]>arr[i-1]。當(dāng)然也滿足arr[i]<arr[i+1]。這就是我們的二段性性質(zhì)。數(shù)組中肯定有一段是滿足我們的性質(zhì)，另一段不滿足我們的性質(zhì)。現(xiàn)在我以 必定滿足 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;

再來看LeetCode 69題

直達(dá)力扣官網(wǎng)查看
https://leetcode.cn/problems/sqrtx/
可以先想一下這道題需要滿足的性質(zhì)是什么，然后再往下看

分析：根據(jù)題目要求，我們要找x的算術(shù)平方根，x的算術(shù)平方根肯定是在0到x之間，所以我們其實(shí)就是在0-x之前找一個數(shù)，但是我們要找x的算術(shù)平方根，結(jié)果只保留整數(shù)部分，其實(shí)就是向下取整。
所以這道題滿足 midmid<=x 其中mid是x的算術(shù)平方根
解釋：因?yàn)橐襵的算術(shù)平方根，如果不向下取整，那么 結(jié)果就是midmid=x。 而現(xiàn)在mid向下取整了，如果x的算術(shù)平方根不是整數(shù)，那就肯定會小于x。
如：8的算術(shù)平方根是2.82842… 向下取整就是2。所以2*2肯定是小于8的

根據(jù)性質(zhì)mid*mid<=x。我們要找的是最滿足條件最右側(cè)值。所以還是套用第二個模板

注意：題目中最大數(shù)是x，所以要把r=nums.length-1改成r=x
題目提示 x的范圍是0——2的31次方-1，所以mid*mid 會出現(xiàn)溢出，所以改成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;
    }
}

總結(jié)

當(dāng)我們拿到一個題目時，首先判斷這個題是否符合二段性質(zhì)，如果符合，那么我們只需要找到這個性質(zhì)，然后套用模板即可；