目錄
-
-
- 一、簡介
- 二、易錯點
- 三、例子
- 四、萬能模闆
- 五、參考資料
-
一、簡介
哪怕沒有學過程式設計的同學，也許不知道二分法這個名字，但也一定接觸過它的核心思想。不了解的同學也沒關系，我用一句話就能概括出它的精髓：将一個區間一分為二，每次都舍棄其中的一部分。
二分法能夠極大地降低我們在解決問題時的時間複雜度。假如你要在一個單調遞增的數組a[n]中尋找一個數target，周遊的話時間複雜度是O(n)。但如果采用二分法，時間複雜度則是O(log n)。這種效率的提高無疑是巨大的！
二、易錯點
1、while循環中是寫 left < right 還是寫 left <= right ？
2、如下圖所示，if(nums[mid]>target)，右邊界更新區間時是寫成 right = mid 還是 right = mid-1？
這兩點是很容易弄混的。要弄清楚上面這兩個問題的答案，首先要确定你想寫的循環的區間到底是
左閉右開
還是
左閉右閉
？（題目沒明确要求的話就看你個人選擇，都是可以的）
左閉右閉的區間是這樣寫的：
[left, right]
它包含了 left 和 right 這兩個數
左閉右閉的區間是這樣寫的：
[left, right)
它包含了 left，但不包含 right 。
假設我選擇了左閉右閉，此時需要在數組nums中尋找一個數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;
}
}
首先，為什麼選擇左閉右閉的區間，第3行就要寫成<=呢？因為寫入while循環的判斷條件應該與你選擇的區間相吻合，而左閉右閉的區間包含了left和right，也就是說可能會出現 left== right的情況。如果寫成<，那麼就漏掉了left==right 這種情況，是以應該寫成<=。
其次，第5行右邊界為什麼更新為 mid-1 而不是更新為 mid？因為我們已經确定了nums[mid] > target，是以mid一定不是我們要找的值，是以在下一輪搜尋中，不應再包含mid這個數。而我們選擇的是左閉右閉區間，它包含了左右邊界，每次搜尋時都會包含左右邊界。是以為了使已經被排除的mid不被再次搜尋，右邊界應該更新為mid-1。
假設我選擇了左閉右開，此時需要在數組nums中尋找一個數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包含在搜尋區間裡。
三、例子
如果你已經了解了上面的内容，可以嘗試做下面這道題：
左閉右閉：
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;
}
};
四、萬能模闆
盡管了解了上面的内容，但很多時候解題還是會遇到困難。
比如說給你一個按照非遞減順序排列的整數數組 nums，和一個目标值 target。請你找出給定目标值在數組中的開始位置和結束位置。
你會發現上面的兩個代碼很難應用到這種題，是以我找到了一個萬能模闆，跟大家分享一下：
class Solution {
/**
* 如果傳回值等于 nums.size()，代表 nums 中不存在 滿足 nums[i] >= target 的 i，也就是所有元素都小于 target。
* 否則傳回滿足 nums[i] >= target 的最小 i（最左 i）。也就是說，如果有多個連續的 target，會傳回最靠左的那個的下标。
* nums為單調不減數組
* 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、查找某個數 x 首次出現的位置，如果不存在，傳回-1。
如果
binarySearch(arr, x) == nums.size()
，代表所有元素都小于x，也就無法查找到 x 首次出現的位置；如果有多個元素等于 x，則
binarySearch(arr, x)
代表 x 首次出現的位置的下标；如果
binarySearch(arr, x) != x
，則不存在某個數等于 x，
binarySearch(arr, x)
代表最靠左的大于 x 的數。
2、查找某個數 x 最後出現的位置，如果不存在，傳回-1。
将該問題轉換為用
int ret = binarySearch(arr, x+1) - 1
來解決。 如果ret < 0，傳回 -1；否則，如果nums[ret] == x，ret 就是答案；否則，傳回 -1。
3、查找某個數 x 首次出現的位置，如果不存在 x，則求出适合插入 x 的位置。
binarySearch(arr, x)
就是。
4、查找小于x的最後一個數。
轉換為用
binarySearch(arr, x) - 1
來解決，注意判斷存在性。
5、查找小于x的第一個數。
這是個僞問題。
6、查找大于x的第一個的數。
轉換為用
binarySearch(arr, x + 1)
來解決，注意判斷存在性。
7、查找大于x的最後一個的數。
這是個僞問題。
舉例：
35. 搜尋插入位置
給定一個排序數組和一個目标值，在數組中找到目标值，并傳回其索引。如果目标值不存在于數組中，傳回它将會被按順序插入的位置。
請必須使用時間複雜度為 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 <= 1 0 4 10^4 104
- - 1 0 4 10^4 104 <= nums[i] <= 1 0 4 10^4 104
- nums 為 無重複元素 的 升序 排列數組
- - 1 0 4 10^4 104 <= target <= 1 0 4 10^4 104
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、【二分查找】詳細圖解
📝我的個人首頁 🎁歡迎各位→點贊👍 + 收藏⭐️ + 留言📝 💬總結：希望你看完之後，能對你有所幫助，不足請指正！共同學習交流 🖊 ✉️今天你做别人不想做的事，明天你就能做别人做不到的事♐