從 n 筆資料中查找目標值：循序搜尋與二分搜尋演算法對比

搜尋是資料處理的基礎操作。本文介紹兩種經典演算法：循序搜尋（適用未排序資料）與 二分搜尋（要求資料已排序），並給出 C 風格函式實作與邏輯解析。

1. 循序搜尋

• 時間複雜度：O(n)
• 適用：資料量小、未排序、單次查詢。
• 邏輯：從索引 0 遍歷至 n-1，逐一比對目標值。

2. 二分搜尋

• 前提：資料已由小到大排序。
• 時間複雜度：O(log n)
• 核心邏輯：
  1. 設定搜尋區間 [low, high]，初始為 [0, n-1]。
  2. 計算中點 mid = (low + high) / 2。
  3. 比較 a[mid] 與目標值 x：
     • 相等 → 找到，回傳索引。
     • a[mid] > x → 目標在左半部，high = mid - 1。
     • a[mid] < x → 目標在右半部，low = mid + 1。
  4. 重複直到 low > high（未找到）或找到為止。

C 函式實作（修正原始碼邏輯錯誤）

int binary_search(const float a[], int n, float x) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // 避免溢位
        if (a[mid] == x) return mid;
        else if (a[mid] > x) high = mid - 1;
        else low = mid + 1;
    }
    return -1; // 未找到
}

關鍵修正說明

• 原始碼 b=d: 應為 b=d+1（或 low = mid + 1），否則陷入無窮迴圈。
• 原始碼 e=d 應為 high = mid - 1，否則區間無法正確收斂。
• 回傳型別改為 int，找到回傳索引，失敗回傳 -1，符合慣例。

效能對比（n=1,000,000）

「二分搜尋是『分治法』教科書級範例：每次將問題規模減半，對數級效能源於資料的有序性。」