二分查找的思路

對于一個有序數組，如果我們想查找指定數值的索引，最樸素的方法就是從頭到尾依次遍歷，但是這樣的時間復雜度是 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;

模板二：找滿足條件的最右側的值

模板代碼：

        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,是最左邊的元素，數組索引都是從0開始，所以寫的是l=0，如果最左邊不是0，那么改成對應的數即可。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。

這兩個模板，其實選擇滿足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;
    }
}

再來看LeetCode 852題

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

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

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

分析：根據題目要求，我們要找x的算術平方根，x的算術平方根肯定是在0到x之間，所以我們其實就是在0-x之前找一個數，但是我們要找x的算術平方根，結果只保留整數部分，其實就是向下取整。
所以這道題滿足 midmid<=x 其中mid是x的算術平方根
解釋：因為要找x的算術平方根，如果不向下取整，那么 結果就是midmid=x。 而現(xiàn)在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 會出現(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;
    }
}

總結

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