二分查找算法完整實現：迭代版與遞歸版 Java 代碼詳解

二分查找是**有序數組**查找的標準算法，時間複雜度 O(log n)。本文提供迭代與遞歸兩種完整 Java 實現，並解析邊界條件、中點計算溢出防護、未找到時的返回值約定。

前提條件

• 數組**必須已排序**（升序）
• 元素可比較（實現 Comparable 或基本類型）

迭代版（推薦，無棧溢出風險）

public static int binarySearch(int[] numbers, int target) {
    int min = 0;
    int max = numbers.length - 1;
    while (min <= max) {
        int mid = min + (max - min) / 2; // 防止 (min+max) 溢出
        if (numbers[mid] == target) {
            return mid; // 找到，返回索引
        } else if (numbers[mid] < target) {
            min = mid + 1; // 目標在右半部
        } else {
            max = mid - 1; // 目標在左半部
        }
    }
    return -min - 1; // 未找到，返回負的插入點-1（Java Arrays.binarySearch 約定）
}

遞歸版（教學演示，注意棧深度）

public static int binarySearch(int[] nums, int start, int end, int target) {
    if (start > end) return -1; // 區間為空，未找到
    int mid = start + (end - start) / 2;
    if (nums[mid] < target) {
        return binarySearch(nums, mid + 1, end, target);
    } else if (nums[mid] == target) {
        return mid;
    } else {
        return binarySearch(nums, start, mid - 1, target);
    }
}

關鍵細節對比

擴展：泛型版本

public static > int binarySearch(T[] arr, T target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int cmp = arr[mid].compareTo(target);
        if (cmp == 0) return mid;
        else if (cmp < 0) lo = mid + 1;
        else hi = mid - 1;
    }
    return -lo - 1;
}

常見錯誤避坑

1. 未排序數組直接調用：結果不可預期
2. mid 計算溢出：用 low + (high-low)/2 而非 (low+high)/2
3. 邊界條件錯誤：while (low < high) vs low <= high 需與更新邏輯配合
4. 遞歸未處理空區間：必須先判 if (start > end) return -1;

二分查找是算法面試必考、工程庫廣泛使用的基石，徹底掌握其正確實現至關重要。