二分搜尋法

前導

二分搜尋法（Binary Search）是一種 高效的搜尋演算法，適用於 已排序 的資料結構。 它的核心思想是 每次將搜尋範圍減半，直到找到目標值或範圍縮小到無法繼續搜尋。

演算法步驟

1. 確認資料已排序（若未排序，需先排序）。
2. 設定 左邊界 (low) 為 0，右邊界 (high) 為陣列長度 - 1。
3. 計算中間索引 (mid)：

4. 比較 arr[mid] 與 target：

• • • 若 arr[mid] == target，則返回索引 mid（找到目標）。
    • 若 arr[mid] > target，則 high = mid - 1（縮小到左半區間）。
    • 若 arr[mid] < target，則 low = mid + 1（縮小到右半區間）。

5. 重複第三步驟和第四步驟。
6. 若 low > high，表示目標值 不存在，返回 -1。

程式碼

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        printf("low = %d, high = %d, mid = %d, arr[mid] = %d\n", low, high, mid, arr[mid]);

        if (arr[mid] == target) {
            return mid;  // 找到目標，返回索引
        }
        if (arr[mid] < target) {
            low = mid + 1;  // 搜尋右半部
        } else {
            high = mid - 1; // 搜尋左半部
        }
    }
    return -1;  // 找不到
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72}; // 已排序數列
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 23;

    int result = binarySearch(arr, size, target);
    if (result != -1) {
        printf("找到 %d，索引位置為 %d\n", target, result);
    } else {
        printf("未找到 %d\n", target);
    }

    return 0;
}

• 與 循序搜尋法 相比，二分搜尋法的效率大幅提升。