您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言折半查找（二分搜尋）標準實作與邊界條件完整解析

編輯：關於C

前提條件

陣列**已排序**（升序）。
隨機存取結構（陣列、Vector）。

標準迴圈版本（推薦）

int binary_search(const int *arr, int n, int target) {
    int left = 0, right = n - 1; // 閉區間 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 未找到
}

關鍵細節

細節	說明
`left + (right-left)/2`	避免 `(left+right)` 溢出（大陣列）
`left <= right`	閉區間終止條件，`left == right` 仍需檢查
`left = mid + 1` / `right = mid - 1`	排除 `mid`，因已檢查過
回傳 `-1`	慣用「未找到」標記，或回傳插入位置 `left`

遞迴版本

int binary_search_rec(const int *arr, int left, int right, int target) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binary_search_rec(arr, mid+1, right, target);
    return binary_search_rec(arr, left, mid-1, target);
}

完整測試程式

#include 

int binary_search(const int *arr, int n, int target) { /* 迴圈版 */ }

int main() {
    int arr[] = {2, 6, 20, 66, 177, 199, 600};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target;
    printf("Enter target: ");
    scanf("%d", &target);
    int idx = binary_search(arr, n, target);
    if (idx != -1) printf("Found at index %d: %d\n", idx, arr[idx]);
    else puts("Not exist");
    return 0;
}