一、簡介

哪怕沒有學過編程的同學，也許不知道二分法這個名字，但也一定接觸過它的核心思想。不了解的同學也沒關系，我用一句話就能概括出它的精髓：將一個區(qū)間一分為二，每次都舍棄其中的一部分。

二分法能夠極大地降低我們在解決問題時的時間復雜度。假如你要在一個單調(diào)遞增的數(shù)組a[n]中尋找一個數(shù)target，遍歷的話時間復雜度是O(n)。但如果采用二分法，時間復雜度則是O(log n)。這種效率的提高無疑是巨大的！

二、易錯點

1、while循環(huán)中是寫 left < right 還是寫 left <= right ？

2、如下圖所示，if(nums[mid]>target)，右邊界更新區(qū)間時是寫成 right = mid 還是 right = mid-1？

這兩點是很容易弄混的。要弄清楚上面這兩個問題的答案，首先要確定你想寫的循環(huán)的區(qū)間到底是左閉右開還是左閉右閉？（題目沒明確要求的話就看你個人選擇，都是可以的）

左閉右閉的區(qū)間是這樣寫的：[left, right]

它包含了 left 和 right 這兩個數(shù)

左閉右閉的區(qū)間是這樣寫的：[left, right)

它包含了 left，但不包含 right 。

假設我選擇了左閉右閉，此時需要在數(shù)組nums中尋找一個數(shù)target，找到的話返回下標，沒找到的話返回 -1，偽代碼如下：

left=0;
right=nums.size()-1;
while(l <= r){ // 注意這里不是 l < r
	int mid = l + (r - l)/2;
	if(nums[mid] > target) right = mid-1;
	else if(nums[mid] < target) left = mid+1;
	else{
		return mid;
	}	
}

首先，為什么選擇左閉右閉的區(qū)間，第3行就要寫成<=呢？因為寫入while循環(huán)的判斷條件應該與你選擇的區(qū)間相吻合，而左閉右閉的區(qū)間包含了left和right，也就是說可能會出現(xiàn) left== right的情況。如果寫成<，那么就漏掉了left==right 這種情況，所以應該寫成<=。

其次，第5行右邊界為什么更新為 mid-1 而不是更新為 mid？因為我們已經(jīng)確定了nums[mid] > target，所以mid一定不是我們要找的值，因此在下一輪搜索中，不應再包含mid這個數(shù)。而我們選擇的是左閉右閉區(qū)間，它包含了左右邊界，每次搜索時都會包含左右邊界。所以為了使已經(jīng)被排除的mid不被再次搜索，右邊界應該更新為mid-1。

假設我選擇了左閉右開，此時需要在數(shù)組nums中尋找一個數(shù)target，找到的話返回下標，沒找到的話返回 -1，偽代碼如下：

left=0;
right=nums.size();
while(l < r){ // 注意這里不是 l <=r
	int mid = l + (r - l)/2;
	if(nums[mid] > target) right = mid;
	else if(nums[mid] < target) left = mid+1;
	else{
		return mid;
	}	
}
return -1;

左閉右開代表包含左邊界，不包含右邊界。右邊界一定比左邊界大，不存在 right == left 的情況。所以第3行只能寫成<。

而第5行之所以寫成right=mid，是因為下一次搜索中本就不會包含right，我們也確定了right不是要找的值，所以直接寫成right=mid就可以了。

此時，注意第2行，因為左閉右開不包含右邊界，所以右邊界要設置為nums.size()，這樣才能把nums.size()-1包含在搜索區(qū)間里。

三、例子

如果你已經(jīng)理解了上面的內(nèi)容，可以嘗試做下面這道題：

左閉右閉：

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

左閉右開：

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

四、萬能模板

盡管理解了上面的內(nèi)容，但很多時候解題還是會遇到困難。

比如說給你一個按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個目標值 target。請你找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。

你會發(fā)現(xiàn)上面的兩個代碼很難應用到這種題，所以我找到了一個萬能模板，跟大家分享一下：

class Solution {
    /**
     * 如果返回值等于 nums.size()，代表 nums 中不存在 滿足 nums[i] >= target 的 i，也就是所有元素都小于 target。
     * 否則返回滿足 nums[i] >= target 的最小 i（最左 i）。也就是說，如果有多個連續(xù)的 target，會返回最靠左的那個的下標。
     * nums為單調(diào)不減數(shù)組
     * target為邊界值  
     **/
    public: int binarySearch(vector<int>& nums, int target) {
        int l = 0, r = nums.size()- 1; // 二分查找的左右初始邊界
        while(l <= r){ // 注意這里不是 l < r
            int m = l + (r - l)/2;
            if(nums[m] >= target)r = --m;
            else l = ++m;
        }
        return l; // 此時，l 代表arr[i] >= x 的最小 i。
    }
};

如何運用這個模板去解決不同的問題呢？請往下看

1、查找某個數(shù) x 首次出現(xiàn)的位置，如果不存在，返回-1。

如果 binarySearch(arr, x) == nums.size()，代表所有元素都小于x，也就無法查找到 x 首次出現(xiàn)的位置；如果有多個元素等于 x，則 binarySearch(arr, x) 代表 x 首次出現(xiàn)的位置的下標；如果binarySearch(arr, x) != x，則不存在某個數(shù)等于 x，binarySearch(arr, x) 代表最靠左的大于 x 的數(shù)。

2、查找某個數(shù) x 最后出現(xiàn)的位置，如果不存在，返回-1。

將該問題轉(zhuǎn)換為用 int ret = binarySearch(arr, x+1) - 1 來解決。 如果ret < 0，返回 -1；否則，如果nums[ret] == x，ret 就是答案；否則，返回 -1。

3、查找某個數(shù) x 首次出現(xiàn)的位置，如果不存在 x，則求出適合插入 x 的位置。

binarySearch(arr, x)就是。

4、查找小于x的最后一個數(shù)。

轉(zhuǎn)換為用binarySearch(arr, x) - 1來解決，注意判斷存在性。

5、查找小于x的第一個數(shù)。

這是個偽問題。

6、查找大于x的第一個的數(shù)。

轉(zhuǎn)換為用binarySearch(arr, x + 1)來解決，注意判斷存在性。

7、查找大于x的最后一個的數(shù)。

這是個偽問題。

舉例：

35. 搜索插入位置

給定一個排序數(shù)組和一個目標值，在數(shù)組中找到目標值，并返回其索引。如果目標值不存在于數(shù)組中，返回它將會被按順序插入的位置。

請必須使用時間復雜度為 O(log n) 的算法。

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2

示例 2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:

• 1 <= nums.length <= $10^4$

• -$10^4$ <= nums[i] <= $10^4$

• nums 為 無重復元素 的 升序 排列數(shù)組

• -$10^4$ <= target <= $10^4$

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r =  nums.size() - 1; // 二分查找的左右初始邊界
        while(l <= r){ // 注意這里不是 l < r
        int m = l + (r - l)/2;
        if(nums[m] >= target)r = --m;
        else l = ++m;
    }
    return l; // 此時，l 代表arr[i] >= tarhget的最小 i。
    }
};

五、參考資料

1、二分查找萬能模板

2、【二分查找】詳細圖解文章來源地址http://www.zghlxwxcb.cn/news/detail-804784.html

到了這里，關于【二分查找】一文帶你掌握二分法 （附萬能模板）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！