📝前言說明：

• 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

二分查找算法介紹

因為我之前用python寫題的時候也寫過二分查找，也有點心得：
https://blog.csdn.net/tan_run/article/details/145514702
如今再學，任深感不足。通過 704 和 34 題再度感受和理解二分查找。

---

704. 二分查找

暴力解法：
遍歷數組，依次和target比較，時間復雜度：O(n)

暴力解法的局限在于：每次只能判斷一個數，沒有利用數組升序的特點

更好的解法：二分查找。利用數組有序的特點，那怎么利用呢？

假設我們隨機取一個下標i，將nums[i]與target比較，如果nums[i] < target，又因為數組有序，所以：nums[i]左邊的數都小于target，我們就可以直接排除左邊的區間。

而上面所體現的也叫做二段性：每次“選點”，通過該點可以讓我們把探索區域劃分成兩份，并且能夠排除一段區域。（只是選中點的時候，數學期望最小（易證），所以我們通常取中點，也叫做二分）

樸素二分查找模板

閉區間寫法：

• .......：根據二段性的特點來填寫
• while(left <= right)：因為是閉區間寫法，區間不為空，還要判斷
• left + (right - left) / 2：防溢出寫法

---

34. 在排序數組中查找元素的第一個和最后一個位置

暴力解法：
從頭到尾遍歷數組，時間復雜度：O(n)

二分查找（利用二段性）：

• 先找左端點：左端點左邊的元素 < t；左端點及左端點右邊的元素 >= t。于是，我們就可以發現二段性：當nums[mid] < t，左端點一定嚴格在mid的右邊[mid + 1, right]（畫圖很好理解） ，left更新為mid + 1；當nums[mid] >= t的時候，左端點一定在[left, mid]，mid位置不能排除，因為有可能mid就是左端點，right更新為mid
• 上面這種方法其實是左閉右開區間的寫法，right所在位置已經判斷過了，循環條件為while(left < right)，因為當 left == right 的時候已經是空區間，循環不變量：right始終指向 >= t 的數字
• 求中點操作：在左閉右開這種寫法里面，當有兩個中間值時（數組長度為偶數），必須要選擇前一個：left + (right - left) / 2

重點：以上總結找左端點>=（左閉右開區間寫法）：

• 如果nums[mid] < t，則右端點肯定在：[mid + 1, right]
• 如果nums[mid] >= t，則右端點肯定在：[left, mid]
• 循環條件，while(left < right)（因為是左閉右開的）
• 求中點操作：left + (right - left) / 2 取前面的中點
• 循環不變量：right始終指向第一個>= t的數

PS：多舉例子，找極端例子看特殊情況

當然我們也可以直接寫找右端點<=的：

• 如果nums[mid] <= t，則右端點肯定在：[mid, right]
• 如果nums[mid] > t，則右端點肯定在：[left, mid - 1]
• 循環條件，while(left < right)（因為是左開右閉）
• 求中點操作：left + (right - left + 1) / 2 取后面的中點

其他方法：在>=的基礎上轉換：

題解代碼：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0){return {-1, -1};}// 二分左端點 >= int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2; // 防止溢出if(nums[mid] < target)left = mid + 1;elseright = mid;}if(nums[right] != target)return {-1, -1}; // 代表沒有targetint begin = right;// 找右端點（左端點不重置）left = begin, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target)left = mid;elseright = mid - 1;}return {begin, right};}
};

二分模板

口訣：

• mid：下面出現 -1，上面就要 +1
• if...else...：根據二段性寫出

為什么呢？

首先，左右兩種模板的取mid區別是：左邊是向下取整，右邊是向上取整

以右邊模板為例：
右邊模板的收縮范圍：[mid, right] 或 [left, mid - 1]
如果此時剩余區間為：[right - 1, right]，向下取整則mid = right - 1。如果，最后的判斷進入if，則left = mid = right - 1和原來無異，就會死循環。
如果是向上取整：mid = right，進入if：left = right，進入else：right = right - 1，兩條語句都變化了，就不會死循環

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！