🎯 算法精講：二分查找（二）—— 變形技巧 🔍

友情提示：：本小節含高能代碼片段 🥤

1. 閱讀前請確保已掌握基礎二分原理與實現
2. 代碼片段可能包含不同程度的變形，請根據實際情況選擇閱讀

作者：無限大

推薦閱讀時間：30min

📚 內容回顧與引言

在上一篇《算法精講：二分查找（一）—— 基礎原理與實現》中，我們剖析了二分查找的核心原理：依賴有序數組的單調性，通過不斷折半搜索快速定位目標值 📈。

重點講解了兩大區間定義方式（左閉右閉 [left, right] 與左閉右開 [left, right)）及其代碼實現細節，并強調了循環不變量原則的重要性。

如果說基礎二分是少林長拳，那各種變形就是奇門遁甲！本篇我們將解鎖二分查找的 “高階技能”，解鎖二分查找的隱藏皮膚 🧥！從基礎的邊界值變形（如找第一個/最后一個等于目標值的位置）到復雜場景應用（如旋轉數組、珂珂吃香蕉問題）。

🧩 一、常見二分變形及應用場景

1. 查找第一個等于目標值的元素位置

思路：在非遞減序列中查找第一個等于目標值的元素。當 arr[mid] == target 時，不立即返回，而是繼續向左查找（即 right = mid - 1），以確保找到的是第一個出現的位置。

代碼實現：

/*** 在含重復元素的有序數組中，找到目標值第一次出現的位置* @param nums 有序數組（可重復）* @param target 目標值* @return 首個等于target的索引，未找到返回-1*/
public int findFirstEqual(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1; // 初始化結果while (left <= right) {int mid = left + (right - left) / 2; // 防溢出計算中點if (nums[mid] == target) {result = mid;    // 記錄位置right = mid - 1; //  👉 關鍵！繼續向左搜索更早出現的目標} else if (nums[mid] < target) {left = mid + 1;  // 目標在右半區} else {right = mid - 1; // 目標在左半區}}return result; // 返回首個位置
}

? 適用場景：統計數字 4 在數組 [1,2,4,4,4,5] 中的起始位置（返回 2）

2. 查找第一個大于等于目標值的元素位置

思路：
目標是找到第一個大于或等于目標值的元素。當 arr[mid] >= target 時，縮小右邊界（right = mid - 1），否則縮小左邊界（left = mid + 1）。循環結束后，直接返回 left，因為它指向第一個大于等于目標值的位置。

代碼實現：

/*** 找到有序數組中首個≥target的元素位置* @param nums 有序數組* @param target 目標值* @return 首個≥target的索引（若target超最大值返回-1）*/
public int findFirstGreaterOrEqual(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1; //  👉 向左收縮，嘗試找到更小的滿足條件的值} else {left = mid + 1;  // 向右擴大搜索}}// 結束時left指向首個≥target的位置return (left < nums.length) ? left : -1;
}

? 典型應用：將數字 3 插入有序數組 [1,2,4,5] 的正確位置（返回 2）

3. 查找第一個大于目標值的元素位置

思路：
尋找第一個大于目標值的元素。當 arr[mid] <= target 時，縮小左邊界（left = mid + 1），否則縮小右邊界（right = mid - 1）。循環結束后，left 指向第一個大于目標值的元素。

/*** 找到有序數組中首個>target的元素位置* @param nums 有序數組* @param target 目標值* @return 首個>target的索引（若target超最大值返回-1）*/
public int findFirstGreater(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) { //  👉 注意條件包含等于left = mid + 1;  // 目標在右半區} else {right = mid - 1; // 向左收縮}}return (left < nums.length) ? left : -1;
}

💡 關鍵點：當 nums[mid] == target 時仍需右移，確保定位到嚴格大于的位置

4. 查找最后一個等于目標值的元素位置

思路：
在非遞減序列中查找最后一個等于目標值的元素。當 arr[mid] == target 時，不立即返回，而是繼續向右查找（即 left = mid + 1），以確保找到的是最后一個出現的位置。循環結束后，檢查 right 是否越界以及 arr[right] 是否等于目標值。

/*** 在含重復元素的有序數組中，找到目標值最后一次出現的位置* @param nums 有序數組* @param target 目標值* @return 最后一個等于target的索引，未找到返回-1*/
public int findLastEqual(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {result = mid;   // 記錄位置left = mid + 1; //  👉 關鍵！繼續向右搜索更晚出現的目標} else if (nums[mid] < target) {left = mid + 1; // 目標在右半區} else {right = mid - 1;// 目標在左半區}}return result;
}

? 用例：確定 4 在 [1,2,4,4,4,5] 中的結束位置（返回 4）

5. 查找最后一個小于等于目標值的元素位置

思路：
目標是找到最后一個小于等于目標值的元素。當 arr[mid] <= target 時，縮小左邊界（left = mid + 1），否則縮小右邊界（right = mid - 1）。循環結束后，right 指向最后一個小于等于目標值的元素。

/*** 找到有序數組中最后一個≤target的元素位置* @param nums 有序數組* @param target 目標值* @return 最后一個≤target的索引（若target小于最小值返回-1）*/
public int findLastLessOrEqual(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {result = mid;     // 記錄可能位置left = mid + 1;   // 👉 向右嘗試找到更大的滿足值} else {right = mid - 1;  // 目標在左半區}}return result;
}

💡 應用場景：統計考試成績 ≤80 分的最高分學生位置

6. 查找最后一個小于目標值的元素位置

思路：
尋找最后一個小于目標值的元素。當 arr[mid] < target 時，縮小左邊界（left = mid + 1），否則縮小右邊界（right = mid - 1）。循環結束后，right 指向最后一個小于目標值的元素。

代碼實現：

/*** 找到有序數組中最后一個<target的元素位置* @param nums 有序數組* @param target 目標值* @return 最后一個<target的索引（若target小于最小值返回-1）*/
public int findLastLess(int[] nums, int target) {int left = 0, right = nums.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {result = mid;     // 記錄位置left = mid + 1;   //  👉 向右嘗試找到更大的滿足值} else {right = mid - 1;  // 目標在左半區}}return result;
}

? 典型場景：在 [10,20,30,40] 中找 <35 的最后位置（返回 2）

六種核心變形對比

💡 核心區別：普通二分找到目標即返回，而變形算法會繼續向特定方向收縮邊界，確保定位到最左/最右的目標值

?? 邊界處理避坑指南

二分變形代碼的 “魔鬼在細節”，90%的 bug 源于邊界處理不當！以下是四大核心避坑點：

1. 初始邊界設置原則

• 右邊界取值：
  • right = length - 1 ? 閉區間搜索（如普通二分）
  • right = length ? 開區間搜索（如插入位置問題），防止漏檢末尾元素

示例：

// 閉區間：搜索范圍[0, length-1]
int right = nums.length - 1;
// 開區間：搜索范圍[0, length)
int right = nums.length;

2. 循環條件選擇策略

黃金法則：

• 用 <=時必須配合 left=mid+1/right=mid-1
• 用 <時必須配合 left=mid+1/right=mid

3. 越界處理技巧

• 返回前必校驗：

  // 檢查left是否越界（開區間場景）
  return (left < nums.length) ? left : -1;
  

• 防 off-by-one 錯誤：

  • 當 left=0或 right=length-1時，mid計算需防溢出 ? mid = left + (right - left) / 2

  • 結束時驗證結果有效性：

    // 查找類需驗證找到的是否為目標值
    if (left >= nums.length || nums[left] != target) return -1;
    

溫馨提示

在編程中，off-by-one（差一錯誤） 指因邊界處理偏差導致的邏輯錯誤，通常表現為循環、索引或區間計算中意外地少或多一次操作。這種錯誤在二分查找中尤為常見，可能導致死循環、漏檢或越界崩潰。

4. 重復元素特判

當數組含重復值時，額外添加分支：

// 旋轉數組場景（解決 [3,1,2,3,3,3,3] 類問題）
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {left++;   // 跳過左側重復right--;  // 跳過右側重復
}

💡 邊界心法口訣：

初值定區間 → 循環控方向 → 退出驗邊界 → 重復要特判

掌握此四步，二分無坑！ 🔥

🚀 二、二分變形之魂：LeetCode 實戰 ?

光說不練假把式，來點硬菜！

案例 1：珂珂吃香蕉（LeetCode 875）

題目：傳送門

場景：珂珂面前堆著 N堆香蕉，警衛 H小時后回來。她每小時只能選一堆吃 K根，吃不完藏枕頭下。求最小吃速 K讓她優雅吃完蕉。

場景翻譯：
當你媽出門時說「H 小時后回來」👩，而你要偷吃掉 N 堆香蕉 🍌…每堆數量隨機！每小時只能選一堆吃 K 根（不夠還得藏枕頭下），求最小吃速 K避免被打 👋

解題思路拆解：

1.為什么用二分：

• 吃速 K存在臨界點：小于它吃不完（太淑女），大于它浪費（變飯桶）

• 暴力枚舉會超時 → 二分搜索完美匹配"找最小可行解"場景

  2.靈魂三問：

• 搜索區間：[1, 最大香蕉堆]（吃速至少為 1，最大不超過最大堆）

• 判斷條件：當前吃速mid能否在H小時內吃完 ?

• 邊界收縮：能吃完就壓榨吃速（right=mid-1），吃不完就加速（left=mid+1）

二分妙用：

public int minEatingSpeed(int[] piles, int h) {int left = 1; // 吃速下限：淑女的矜持（至少1根/小時）int right = 0;for (int pile : piles) right = Math.max(right, pile); //  👉 最大堆即吃速上限// 🔥 二分奧義：在[1,最大堆]區間反復橫跳測試，看看哪個速度能吃完香蕉while (left <= right) {int mid = left + (right - left) / 2; // mid=當前測試吃速if (canFinish(piles, mid, h)) {right = mid - 1; //  🙆♀? 能吃完？再壓榨下吃速！} else {left = mid + 1; //  🙅♂? 吃不完？加速干飯！}}return left; // 返回最小吃速K
}private boolean canFinish(int[] piles, int speed, int h) {int hoursNeeded = 0;for (int pile : piles) {// ? 騷操作：整數除法向上取整（pile+speed-1）相當于數學ceil()hoursNeeded += (pile + speed - 1) / speed;if (hoursNeeded > h) return false; //  ? 超時警告}return true;
}

關鍵點：

1.mid 是當前測試的吃香蕉速度

2.canEatAll 返回 true → 還能壓榨更小 K！（收縮右邊界）

3.搜索區間右邊界初始化為 max(piles)而非固定值，更通用

關鍵技巧：

🌀 案例 2：旋轉數組搜索（LeetCode 33）🎡

題目：傳送門

場景：數組 [0,1,2,4,5,6,7]旋轉后變 [4,5,6,7,0,1,2]，如何在旋轉數組中搜 target？

破局點：旋轉后必有一半有序！記住這個黃金定律

代碼的藝術：

public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) return mid; //   歐皇附體// 左半邊有序情景 [4,5,6,7,...]if (nums[left] <= nums[mid]) {if (nums[left] <= target && target < nums[mid]) {right = mid - 1; //  👈 target在有序左半區} else {left = mid + 1; //  👉 目標在混亂右半區}}// 右半邊有序情景 [...,0,1,2]else {if (nums[mid] < target && target <= nums[right]) {left = mid + 1; // 👉 target在有序右半區} else {right = mid - 1; // 👈 目標在混亂左半區}}}return -1; //  😭 非酋結局
}

精髓：

• 先判斷哪半邊有序 🔍
• 再判斷 target 是否在有序區間內

避坑指南：

• 比較時用<=而不是<，處理重復元素邊界

• 判斷有序區間時，nums[left] <= nums[mid]中的=處理單元素情況

• 亂中有序，二分永不為奴！

💎 三、二分終極奧義：抽象建模大法 🌌

你以為二分只能搜數組？Noooo，格局打開！凡是能分成兩段性的問題，皆可二分！

萬能二分模板（背會秒殺 80%題）??

while (left <= right) {int mid = left + (right - left) / 2; // 防溢出if (condition(mid)) {right = mid - 1; // 向左側探索} else {left = mid + 1; // 向右側探索}
}
return left; // 魔法值：可能是解/插入位置

四大抽象場景總結 🧩

🏁 四、課后作業大禮包 📚

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

給定升序數組`nums`和目標值`target`，返回`target`的起始和終止位置，不存在則返回`[-1,-1]`  
示例：  
輸入：`nums = [5,7,7,8,8,10], target = 8`  
輸出：`[3,4]`

2. 進階篇：162. 尋找峰值

if (nums[mid] < nums[mid + 1]) {left = mid + 1; //  📈 上升趨勢，峰值在右
} else {right = mid; // 📉 下降趨勢，峰值在左
}

3. 地獄篇：410. 分割數組的最大值

while (left <= right) {int mid = (left + right) / 2;if (canSplit(nums, mid, m)) { // 判斷是否能分成m段且每段和<=midright = mid - 1; // 能分割，嘗試更小的最大值} else {left = mid + 1; // 不能分割，增大最大值}
}
return left; // 最小化最大分段和

數組: [7,2,5,10,8]  m=2
最小最大和：18 →  [7,2,5] 和 [10,8]

本篇關鍵收獲

• 變形本質：普通二分找到即返回，變形需向特定方向收縮邊界（左/右）。

• 抽象心法：凡問題具兩段性（如可行/不可行分界），皆可二分。

• 必記技巧：防溢出中點計算、循環不變量維護。

? 無限大忠告：把代碼復制到 IDE，開啟調試模式觀察邊界變化！

遇到 bug 時：

1. 喝口水 ?

2. 畫邊界圖 📊

3. 默念"循環不變量"三遍 🧘

4. 點這里看解法（別真點，自己思考！）

5. 歡迎各位在評論區分享你的解題思路！

（未完待續：下一篇預告《二分的時空幻術——復雜度與優化篇》）🔥