C 語言折半查找函數正確實作與錯誤修正

C 語言折半查找函數正確實作與錯誤修正

原始碼錯誤分析

// 原始錯誤片段
char arr[] = {1,3,4,6,7,8,56,67,78}; // 應為 int 陣列
int size = strlen(arr); // strlen 用於字串，非整數陣列
if (left = right) // 賦值而非比較
// mid 計算方式不標準

修正後完整程式

#include <stdio.h>

int binary_search(const int arr[], int len, int target) {
    int left = 0, right = len - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (target == arr[mid]) return mid;
        else if (target > arr[mid]) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 4, 6, 7, 8, 56, 67, 78};
    int len = sizeof(arr) / sizeof(arr[0]);
    int target;
    printf("輸入查找值: ");
    scanf("%d", &target);
    int idx = binary_search(arr, len, target);
    if (idx != -1)
        printf("找到 %d 於索引 %d\n", target, idx);
    else
        printf("不存在\n");
    return 0;
}

修正重點

1. 陣列型別：改為 int，strlen 僅適用字串。
2. 長度計算：sizeof(arr)/sizeof(arr[0])。
3. 邏輯判斷：if (left == right) 或直接用返回值判斷。
4. 中間值：left + (right-left)/2 防溢位。
5. 返回值：找到返回索引，否則 -1。

測試案例

輸入: 4  -> 找到 4 於索引 2
輸入: 10 -> 不存在

掌握標準二分搜尋模板，避免低級錯誤，是演算法面試必備基本功。