演算法筆記：二分搜尋法的優雅與陷阱

Aionyx

December 23, 2025

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky. — Donald Knuth

核心概念

二分搜尋法 (Binary Search) 是一種在已排序陣列中尋找特定元素的演算法。

複雜度分析

每次迭代搜尋範圍縮半，時間複雜度為：

O(log n)

C++ 實作與陷阱

** 注意：Integer Overflow (整數溢位)**

若計算中間點寫成 (left + right) / 2，當數字很大時相加會變成負數。 安全的寫法應該是 left + (right - left) / 2。

以下是安全的 C++ 實作範例：

#include <vector>
#include <iostream>

int binarySearch(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    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 - 1;
        }
    }
    return -1; // Not found
}