二分查找算法詳解：原理、實現與注意事項

二分查找算法詳解

二分查找（Binary Search），又稱折半查找，是一種在有序數組中高效查找目標值的算法。其核心思想是利用數組的有序特性，每次將查找範圍縮小一半，直到找到目標值或確定不存在。

算法原理

設定三個變量 low、mid、high 分別指向數組的起始、中間和末尾索引。將目標值 key 與中間元素 a[mid] 比較：

• 若相等，查找成功，返回索引 mid。
• 若 key < a[mid]，說明目標在左半部分，令 high = mid - 1。
• 若 key > a[mid]，說明目標在右半部分，令 low = mid + 1。

重複上述過程，直到 low > high 時查找失敗。

關鍵實現細節

為避免整數溢出，計算中間索引時建議使用 mid = low + (high - low) / 2。此外，更新邊界時必須加減 1（即 high = mid - 1、low = mid + 1），否則當目標值不存在時可能陷入無限循環。

代碼示例

int binary_search(int a[], int n, int x) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = low + (high - low) / 2; // 防止溢出
        if (a[mid] == x)
            return mid;
        else if (a[mid] > x)
            high = mid - 1; // 關鍵：必須 -1
        else
            low = mid + 1;  // 關鍵：必須 +1
    }
    return -1; // 未找到
}

複雜度分析

• 時間複雜度：O(log n)，每次比較都將問題規模減半。
• 空間複雜度：O(1)，僅使用常數額外空間。

適用場景與限制

二分查找要求數組必須有序。若數據頻繁插入/刪除，維護有序性成本較高，此時可考慮二叉搜索樹或哈希表等數據結構。