二分查找算法詳解：原理、實現與性能分析

前言：為什麼需要二分查找？

在學習二分查找前，先了解一下順序查找：它對數組逐個掃描，時間複雜度為 O(n)，對於大數據量極其低效。二分查找利用有序數組的特性，每次將搜索範圍減半，時間複雜度降為 O(log n)，是查找算法的基石之一。

核心思想

二分查找的邏輯很直觀：

1. 在有序數組中取中間元素
2. 若目標值等於中間元素，查找成功
3. 若目標值小於中間元素，在前半部分繼續查找
4. 若目標值大於中間元素，在後半部分繼續查找
5. 重複上述過程，直到找到或搜索範圍為空

算法步驟詳解

假設：

• 目標值：MyNum
• 數組：Array，長度為 N
• 搜索區間：[First, Last]（含首含尾）
• 中間索引：Mid = (First + Last) / 2
• 中間值：Mid_Value = Array[Mid]

三種情況分析

情況一：命中

if (Array[Mid] == MyNum) 
    return Mid; // 找到，返回索引

情況二：目標值較小，搜索前半部分

if (MyNum < Mid_Value) {
    // 新搜索區間：[First, Mid - 1]
    Last = Mid - 1; // 關鍵：Last 移動到 Mid - 1
}

注意： 新區間為 [First, Mid - 1]，不包含 Mid，因為 Mid 已經比較過了。

情況三：目標值較大，搜索後半部分

if (MyNum > Mid_Value) {
    // 新搜索區間：[Mid + 1, Last]
    First = Mid + 1; // 關鍵：First 移動到 Mid + 1
}

終止條件

查找循環在以下兩種情況終止：

1. 找到目標值：返回索引
2. 搜索區間為空：First > Last（或 First >= Last 視具體實現），返回「未找到」標識（如 -1）

時間複雜度分析

每次循環將問題規模減半，最多需 log₂N 次比較：

• 最好情況：O(1) —— 一次命中
• 最壞/平均情況：O(log n)
• 空間複雜度：O(1)（迭代實現）

實戰：如何測量算法執行時間？

理解算法複雜度固然重要，實際測量執行時間能直觀對比不同算法/實現的性能。以下是一個簡易計時器類的設計思路：

class Timer {
public:
    Timer();           // 構造函數
    void start();      // 開始計時
    void stop();       // 停止計時
    double time() const; // 返回經過時間（秒）
};

// 使用示例
Timer t;
t.start();
// 執行待測代碼，如 Search()
t.stop();
double elapsed = t.time(); // 獲取耗時（秒）

這樣就能在不依賴外部工具的情況下，快速對比順序查找與二分查找的實際性能差異。

關鍵點總結

• 前提條件：數組必須有序
• 邊界處理：First = Mid + 1 / Last = Mid - 1 是避免死循環的關鍵
• 溢出風險：大數組中 (First + Last) / 2 可能溢出，建議用 First + (Last - First) / 2
• 遞歸 vs 迭代：迭代版本空間效率更高，遞歸版本代碼更簡潔

練習建議

「主要是理解，多練。」嘗試手寫迭代版和遞歸版二分查找，並在 LeetCode 等平台練習相關題目（如 704. 二分查找、35. 搜索插入位置、34. 在排序數組中查找元素的第一個和最後一個位置）。