.

.

前言

本專欄上篇博客已經把滑動指針收尾啦
現在還是想到核心——一段連續的區間，有時候加上哈希表用起來很爽
今天我們來學習新的算法知識——二分查找，相信大家都不陌生
二分查找，怎么說呢，清晰了解之后，其實代碼就幾行
話不多說，跟我一起來瞅瞅吧

二分查找

首先我們來學習兩道經典例題，有了例題和板子，才能更好的擴展和延伸，應對不同的場景
二分查找

其實乍一看，直接遍歷一遍不就好了嗎，但是今天我們的主題是二分查找
所以這一題來學習一下二分的第一個最簡單的板子
解法一就是暴力循環找目標值
解法二：

其實核心就是二段性，只要給的數據有二段性，我們就能用二分
最樸素的就是不斷的找 mid 然后判斷 ，再進到新的區間 ，不斷二分
看看這題代碼，其實大家應該都會寫的，最基礎的二分板子

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

可能覺得二分就這么簡單嗎？？ 不不不，還有另外兩個板子，會有點麻煩
在排序數組中查找元素的第一個和最后一個位置

這題能把另外兩個二分的板子完美詮釋出來，在做這一題之前，我們先來了解兩種情況
前面我們的樸素版本就是 大于 等于 小于 三種情況。
現在我們來想想 左邊區間是小于目標值 右邊區間是大于等于目標值 兩種情況怎么處理
也就是找區間的左端點，如下圖：

相比于前面的樸素板子，有很多細節差別
—left 和 right 的更新， 當 x 小于目標值時，那就是左邊區間，這時候left——mid的區間都是不滿足條件的，因為左邊區間都是小于目標值，所以 left 要更新為 mid+1 ，當 x 大于等于目標值時，因為我們右邊區間默認是大于等于目標值的區間，我們的 right 如果更新為 mid - 1，有可能當前的mid就是要找尋的點，所以 right 應該更新為 mid
—循環條件 當 left == right 時，就是我們要找的答案，這個時候如果循環條件為 left<=right ,會進入死循環
—mid的取值，看下圖，假設就剩下兩個值，目標值是left，先用第一種方法 mid 就是 left，這個時候 x >= 目標值，所以right == mid，剛好left 和 right 相等，找到目標值，如果取用第二種方法，取mid為right，這個時候 x >= 目標值，right 和 mid 相等，然后left還是小于right，死循環，所以當我們把區間分成左邊完全小于目標值，右邊大于等于目標值的時候，就用第一種。

左端點結束了，接下來就是右端點了
也就是左邊區間小于等于目標值，右邊區間完全大于目標值

需要注意的細節還是
—left 和 right 的更新 ，當 x > 目標值的時候 right更新為 mid - 1，因為右邊區間都是大于目標值的， 當 x <= 目標值的時候， left更新為mid，因為左邊區間小于等于目標值，可能mid的位置就是目標值
—left < right left 不能等于 right
—還是 mid 的取值問題，再來回到這個圖
我們先使用第一種，當right為目標值時，更新 mid 是剛好為 left，這個時候left更新為mid，right還是大于left，陷入死循環，使用第二種的話，更新mid為right，left更新為mid，也就是right，left和right相等，跳出循環，找到目標值。所以當區間分成左區間小于等于，右區間大于時，用第二種取mid

好了，找左右端點我們都學會了這題，也是能穩穩拿下了
題目要求找到目標值的左右端點，那我們來一次找左端點的操作，再來一次右端點的操作就好啦，話不多說，上代碼

class Solution 
{
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0)return{-1, -1};int begin = 0;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[left] != target) return {-1, -1};begin = left;right = nums.size() - 1;while(left < right)  //  找右端點{int mid = left + (right - left + 1) / 2;if(nums[mid] > target)right = mid - 1;elseleft = mid;}return {begin, right};}
};

搜索插入的位置

思路

這題看來就是左區間小于，又區間大于等于，二段性就分好啦
假設插入的坐標是x，那么x左邊都是小于目標值的，右區間都是大于等于目標值的
我們可以用查詢左端點的板子，直接返回找到的左端點
還有一種特殊情況就是，數據插入在末尾，原本的數據全部小于目標值的，就把這一點處理一下就好了
話不多說，上代碼

class Solution 
{
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target)  //  特殊情況，所有數據都比目標值小left = mid + 1;		//	返回right + 1elseright = mid;}if(nums[left] < target)return left + 1;elsereturn right;} 
};

x的平方根

思路

本題第一種思路就是暴力枚舉就好了，0-x/2區間一個一個枚舉，挺簡單的思路，就不多贅述了
第二種思路就是二分，我們可以用右端點的板子，設定 i * i <= x為條件，進行二分，最終返回的就是小于等于算數平方根的下標， 話不多說，上代碼

class Solution 
{
public:int mySqrt(int x) {if(x == 0)return 0;long long right = x / 2, left = 1;while(left < right){long long  mid = left + (right - left + 1) / 2; // 查詢右端點取中點處理if(mid * mid > (long long)x)right = mid - 1;elseleft = mid;}return left;        }
};

其實核心就是找到數據的二段性，然后看情況選擇二分查找左端點還是右端點就好啦

山脈數組的峰頂索引

思路

題目的意思是找到山脈的頂峰，第一種思路當然就是暴力查找了，找到最大值就行
第二種思路就是我們可以把山脈分成兩份，二段性不就來了嘛，一段單調增，一段單調減
然后根據情況查找左端點或者右端點就好啦
我們把左區間設定為遞增到山頂的區間，右區間就是下山的區間
這個時候應該用我們的查詢右端點的板子，然后我們的判斷條件可以設為 arr[mid] > arr[mid - 1]
話不多說，看代碼

class Solution 
{
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] > arr[mid - 1]) left = mid;elseright = mid - 1;}return left;}
};

當然，也可以用查詢左端點的板子來寫

class Solution 
{
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2;while(left < right){int mid = left + (right - left) / 2;if(arr[mid] > arr[mid + 1]) right = mid;elseleft = mid + 1;}return left;}
};

其實，核心就是找到二段性，然后再找判斷條件

尋找旋轉排序數組中的最小值

思路

題目的二段性意思已經寫在臉上了，如圖

我們直接設定右端點為 x ，然后上查找左端點的板子，這個x用來判斷區間條件
就是兩步，二段性，區間條件，話不多說，上代碼

class Solution 
{
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;int x = nums[right];while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > x) //  當前值大于  x  表示在左區間left = mid + 1;   //  更新leftelseright = mid;}return nums[left];}
};

總結

二分查找是一種高效的搜索算法，核心在于利用數據的二段性將區間不斷二分，快速定位目標。本文通過經典例題解析了三種常見場景的二分應用：

1. 基本查找：適用于有序數組，通過比較中間值與目標調整區間，時間復雜度O(logN)。
2. 邊界查找：
   • 左邊界：右區間≥目標，循環條件left<right，mid取左中點，更新策略確保不遺漏可能解。
   • 右邊界：左區間≤目標，mid取右中點，避免死循環。
3. 特殊場景：如山脈數組峰值、旋轉數組最小值，通過分析數據規律（如單調性變化點）構造二段性條件。

關鍵點：

• 循環條件選擇（left<right或left<=right）。
• mid計算方式（防止溢出）與邊界更新策略。
• 處理目標不存在或越界的特殊情況。

掌握二分查找的核心在于理解區間劃分邏輯，靈活選擇模板，結合問題特點設計判斷條件，從而高效解決復雜查找問題

今天的內容就到這里啦，不要走開小編持續更新中~~~