前言
二分查找(Binary Search)是一種高效的查找算法，時間復雜度為O(log n)。它適用于已排序的數組或列表。本文將詳細介紹二分查找的兩種常見寫法：閉區間寫法和左閉右開區間寫法。
一、二分查找基本思想
二分查找的核心思想是"分而治之"：
- 將查找區間分成兩部分
- 比較中間元素與目標值
- 根據比較結果決定繼續在左半部分或右半部分查找
- 重復上述過程直到找到目標值或確定目標值不存在
二、閉區間寫法 [left, right]
閉區間寫法中，查找區間包含左右邊界，即[left, right]。
代碼實現
#include <vector>
using namespace std;int binarySearchClosed(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 閉區間包含右邊界while (left <= right) { // 1.注意是<=int mid = left + (right - left) / 2; // 2.防止溢出if (nums[mid] == target) {return mid; // 找到目標} else if (nums[mid] < target) {left = mid + 1; // 3.搜索右半部分} else {right = mid - 1; // 4.搜索左半部分}}return -1; // 未找到
}
關鍵點說明
-
初始化：
right = len(nums) - 1，因為要包含最后一個元素 -
循環條件：
left <= right，因為當left == right時區間[left, right]仍然有效 -
邊界更新：
left = mid + 1：因為nums[mid]已經檢查過，可以排除right = mid - 1：同理
三、左閉右開區間寫法 [left, right)
左閉右開區間寫法中，查找區間包含左邊界但不包含右邊界，即[left, right)。
代碼實現
int binarySearchLeftClosed(vector<int>& nums, int target) {int left = 0;int right = nums.size(); // 右邊界不包含while (left < right) { // 注意是<int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1; // 搜索右半部分} else {right = mid; // 注意不是mid-1}}return -1;
}
關鍵點說明
-
初始化：
right = len(nums)，因為右邊界不包含 -
循環條件：
left < right，因為當left == right時區間[left, right)無效 -
邊界更新：
left = mid + 1：與閉區間相同right = mid：因為右邊界不包含，所以不需要mid - 1
四、兩種寫法的比較
| 特性 | 閉區間寫法 | 左閉右開區間寫法 |
|---|---|---|
| 初始化右邊界 | len(nums)-1 | len(nums) |
| 循環條件 | left <= right | left < right |
| 右邊界更新 | right = mid - 1 | right = mid |
| 區間含義 | [left, right] | [left, right) |
| 終止條件 | left > right | left == right |
五、實際應用中的選擇
兩種寫法都是正確的，選擇哪一種主要取決于個人習慣和具體場景：
-
閉區間寫法：
- 更直觀，區間定義明確
- 邊界更新對稱（left=mid+1, right=mid-1）
-
左閉右開區間寫法：
- 右邊界初始化更簡單（直接使用nums.size）
- 在某些變種問題中可能更方便
六、例題展示
例題鏈接：704. 二分查找 - 力扣（LeetCode）
解答：
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){int mid = (right - left) / 2 + left;int num = nums[mid];if (num == target) {return mid;} else if (num > target) {right = mid - 1;} else {left = mid + 1;}}return -1;}
};
七、常見錯誤與注意事項
- 溢出問題：計算mid時使用
left + (right - left) // 2而不是(left + right) // 2，防止left和right很大時相加溢出 - 邊界更新錯誤：確保在左閉右開寫法中不要錯誤地使用
right = mid - 1 - 循環條件混淆：注意兩種寫法的循環條件不同
- 未排序數組：二分查找要求輸入數組必須是有序的
八、總結
二分查找是一種高效且常用的算法，掌握其兩種區間寫法對于解決各種變種問題非常有幫助。理解區間定義和邊界更新規則是關鍵，建議通過大量練習來熟練掌握這兩種寫法。
希望這篇博客能幫助你更好地理解二分查找算法！在實際編程中，可以根據具體情況和個人偏好選擇適合的寫法。
