二分查找算法詳解：原理、代碼實現與邊界條件完整指南

前言：為什麼二分查找是必考基本功？

二分查找（Binary Search）是計算機科學中最基礎、最高效的查找算法之一，時間複雜度 O(log n)，空間 O(1)。雖然思想簡單，但邊界條件處理是 Bug 溫床（著名的「90% 程式員寫不對二分查找」）。本文從原理推導、標準模板、變體應用、常見陷阱四個維度，助你徹底掌握二分查找。

一、核心原理與前置條件

• 前提：數據結構為順序存儲（陣列/Vector），且關鍵字有序（遞增或遞減）。
• 思想：每次取中間元素與目標比較，根據有序性丟棄一半區間，直到找到或區間為空。

二、標準模板（遞增序列，返回目標索引，不存在返回 -1）

int binarySearch(const vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1; // 閉區間 [lo, hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // 防溢出寫法
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1; // 未找到
}

關鍵點解析

1. 閉區間 [lo, hi]：循環條件 lo <= hi，區間為空時 lo > hi 退出。
2. mid 計算：lo + (hi - lo) / 2 避免 lo + hi 溢出（雖現代 64 位系統較少見）。
3. 邊界收縮：lo = mid + 1 / hi = mid - 1，確保區間嚴格縮小，避免死循環。

三、四大常見變體（面試高頻）

統一模板：左閉右開區間 [lo, hi)

int lowerBound(const vector<int>& arr, int target) {
    int lo = 0, hi = arr.size(); // hi = n，不減 1
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo; // 第一个 >= target 的位置，可能為 n
}

優勢：lo < hi 循環條件、hi = mid 不用 -1、退出時 lo == hi 即答案，極難出錯。

四、實戰陷阱與避坑指南

1. 整數溢出：用 lo + (hi - lo) / 2 或 (lo + hi) >>> 1（無符號右移）。
2. 死循環：邊界更新必須縮小區間。若 lo = mid 或 hi = mid，需配合 lo < hi 且 mid 取下中位（(lo+hi)/2）或上中位（(lo+hi+1)/2）。
3. 重複元素：標準模板返回「任一」匹配位置；若需第一個/最後一個，必須用變體模板。
4. 空陣列/單元素：模板天然兼容（hi = 0 或 1，循環正常執行）。
5. 浮點數比較：避免直接 ==，引入 eps 或用整數放大比較。

五、擴展應用：在「答案空間」上二分

二分不限於陣列索引，任何單調謂詞 P(x)：「x 滿足條件」隨 x 遞增從 false 變 true（或反過來），均可二分答案。

int mySqrt(int x) {
    if (x < 2) return x;
    long lo = 1, hi = x / 2; // 答案在 [1, x/2]
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * mid <= x) lo = mid + 1;
        else hi = mid - 1;
    }
    return hi; // 最後一個 mid*mid <= x 的值
}