Java 二分查找實作與拔出法優化詳解

二分查找基礎

二分查找要求陣列已排序，每次比較中間元素，將搜尋範圍縮減一半，時間複雜度 O(log n)。

標準實作（迭代版）

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 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; // 未找到
}

遞歸版本

public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    return arr[mid] < target
        ? binarySearchRecursive(arr, target, mid + 1, right)
        : binarySearchRecursive(arr, target, left, mid - 1);
}

拔出法優化：尋找邊界值

「拔出法」指針對特定條件（如第一個大於目標值、最後一個小於等於目標值）的變體。

尋找第一個大於等於 target 的索引（lower_bound）

public static int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left; // 可能等於 arr.length
}

尋找最後一個小於等於 target 的索引

public static int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left - 1; // 可能為 -1
}

實戰範例：可比較物件陣列查找

配合 Comparable 介面，支援泛型二分查找。

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

注意事項

• 避免整數溢位：使用 left + (right - left) / 2 而非 (left + right) / 2。
• 確認陣列已按比較器規則排序。
• 回傳 -1 表示未找到，呼叫端需檢查。