一、核心原理與特性

二分查找是一種**對數(shù)時間復(fù)雜度(O(log n))**的高效搜索算法46，需滿足兩個前提條件：

1. 數(shù)據(jù)存儲在連續(xù)內(nèi)存空間（如數(shù)組）
2. 數(shù)據(jù)按升序/降序有序排列35

算法通過折半比較縮小搜索范圍：

• 初始化左右邊界left=0、right=length-1
• 計算中間位置mid = left + (right - left)/2（避免整數(shù)溢出）
• 比較arr[mid]與目標值，調(diào)整左右邊界18

---

二、標準實現(xiàn)步驟（C++迭代版）

Cpp

int binarySearch(int arr[], int size, int target) { int left = 0, right = size - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; // 未找到 }

關(guān)鍵點：

• 循環(huán)終止條件left <= right確保完整搜索區(qū)間覆蓋48
• 邊界調(diào)整時mid±1避免死循環(huán)4

---

三、邊界處理進階

1. 查找第一個/最后一個匹配項

Cpp

// 查找第一個等于target的位置 int findFirst(int arr[], int size, int target) { int left = 0, right = size - 1, res = -1; while (left <= right) { int mid = left + (right - left)/2; if (arr[mid] >= target) { right = mid - 1; if (arr[mid] == target) res = mid; } else { left = mid + 1; } } return res; }

此變體通過記錄臨時結(jié)果處理重復(fù)元素26

2. 旋轉(zhuǎn)數(shù)組查找

適用于部分有序數(shù)組（如[4,5,6,7,0,1,2]）：

• 通過比較arr[mid]與左右邊界判斷有序區(qū)間
• 調(diào)整搜索方向至目標可能存在的區(qū)域76

---

四、應(yīng)用場景與優(yōu)化

場景類型	適用案例	優(yōu)化策略
精確匹配	有序數(shù)組元素定位	標準二分法
范圍查找	統(tǒng)計成績分布、查找IP歸屬地	邊界變體(lower/upper_bound)
數(shù)學問題轉(zhuǎn)化	求平方根、尋找峰值	調(diào)整比較條件
工程實踐	數(shù)據(jù)庫索引、緩存查找	結(jié)合跳表等數(shù)據(jù)結(jié)構(gòu)

---

五、調(diào)試工具推薦

1. Valgrind：檢測內(nèi)存越界問題1
2. 邊界測試用例：
   • 目標為第一個/最后一個元素
   • 數(shù)組中全為相同元素
   • 空數(shù)組或單元素數(shù)組

完整代碼實現(xiàn)和進階案例可參考146中的項目實例。當處理動態(tài)數(shù)據(jù)集時，建議結(jié)合平衡二叉搜索樹(STL中的set/map)實現(xiàn)高效插入與查找。