C語言二分查找：binsearch 函數標準實現

C語言二分查找：binsearch 函數標準實現

在有序數組中查找目標值，返回索引或 -1。標準二分查找模板，含邊界處理、中間值計算防溢出。

標準實現

#include <stdio.h>
#include <stdlib.h>

int binsearch(int x, int arr[], int left, int right) {
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防溢出
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {2, 6, 20, 66, 177, 199, 600};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target;
    printf("輸入查找值：");
    scanf("%d", &target);
    int idx = binsearch(target, arr, 0, n - 1);
    if (idx != -1) printf("找到：arr[%d]=%d\n", idx, arr[idx]);
    else printf("不存在\n");
    system("pause");
    return 0;
}

關鍵點

• 前提：數組必須有序（升序）
• 中間值：mid = left + (right-left)/2 防止 left+right 溢出
• 邊界：left <= right 閉區間，更新 left=mid+1/right=mid-1
• 返回：找到返回索引，未找到返回 -1
• 時間：O(log n)

常見變體

// 查找第一個 >= x 的位置 (lower_bound)
int lower_bound(int x, int a[], int n) {
    int l = 0, r = n;
    while (l < r) {
        int m = l + (r-l)/2;
        if (a[m] < x) l = m + 1;
        else r = m;
    }
    return l;
}

// 查找最後一個 <= x 的位置
int upper_bound(int x, int a[], int n) {
    int l = 0, r = n;
    while (l < r) {
        int m = l + (r-l)/2;
        if (a[m] <= x) l = m + 1;
        else r = m;
    }
    return l - 1;
}

遞歸版本

int binsearch_rec(int x, int a[], int l, int r) {
    if (l > r) return -1;
    int m = l + (r-l)/2;
    if (a[m] == x) return m;
    if (a[m] < x) return binsearch_rec(x, a, m+1, r);
    return binsearch_rec(x, a, l, m-1);
}