C語言術語辨析：對分查找就是二分查找，無異議

結論先行

對分查找 = 二分查找 = Binary Search。這是同一算法的不同中文譯名，無任何技術差異。

術語來源

• 二分查找：直譯 "Binary Search"，強調每次將搜索區間「分成兩半」。
• 對分查找：意譯，強調「對半分割」的動作特徵。早期計算機教材 (如譚浩強系列) 常用此稱呼。
• 折半查找：另一常見譯名，語義完全一致。

算法核心不變

無論叫什麼名字，核心邏輯永遠是：

1. 前提：有序數組 (升序或降序)。
2. 過程：取中間元素與目標值比較 → 相等返回 → 目標較小則搜索左半部 → 目標較大則搜索右半部 → 重複直到找到或區間為空。
3. 複雜度：時間 O(log n)，空間 O(1) (迭代版) 或 O(log n) (遞歸版棧空間)。

標準代碼模板 (迭代版)

int binary_search(const int arr[], int n, int target) {
    int left = 0, right = n - 1;
    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; // 未找到
}

常見變體 (面試高頻)

避坑指南

• 死循環：邊界更新未排除 mid (如 left = mid 或 right = mid 且循環條件為 left < right)。
• 溢出：mid = (left + right) / 2，修正為 left + (right - left) / 2。
• 邊界條件：區間定義不一致 (閉區間 [l, r] vs 左閉右開 [l, r)) 導致循環條件與更新邏輯錯位。
• 未排序輸入：二分查找嚴格要求有序，無序數組必須先排序 (O(n log n)) 或用哈希表 (O(n))。

總結

名字不重要，掌握「有序 + 分半 + 收斂」的核心模型，熟練寫出正確的邊界控制代碼，並能靈活變體解決「第一個/最後一個/區間邊界」等實際問題，才是二分查找 (對分/折半) 的真諦。