Java 二分查找 (Binary Search) 完整實現與變體：標準版、左邊界、右邊界

二分查找核心前提

• 資料結構：有序陣列 (升序或降序)
• 存取方式：隨機存取 O(1) (陣列、ArrayList)
• 時間複雜度：O(log n)
• 空間複雜度：O(1) 迭代版 / O(log n) 遞迴版

標準版：查找目標值是否存在

public class BinarySearch {

    /**
     * 標準二分查找：返回目標值索引，不存在返回 -1
     * @param arr 升序陣列
     * @param target 目標值
     * @return 索引或 -1
     */
    public static int binarySearch(int[] arr, int target) {
        if (arr == null || arr.length == 0) return -1;

        int left = 0;
        int right = arr.length - 1; // 閉區間 [left, right]

        while (left <= right) { // 區間不為空
            int mid = left + ((right - left) >> 1); // 防溢位
            if (arr[mid] == target) {
                return mid; // 找到
            } else if (arr[mid] < target) {
                left = mid + 1; // 目標在右半
            } else {
                right = mid - 1; // 目標在左半
            }
        }
        return -1; // 未找到
    }

    // 測試
    public static void main(String[] args) {
        int[] data = {1, 3, 5, 7, 9, 11, 13};
        System.out.println(binarySearch(data, 7));  // 3
        System.out.println(binarySearch(data, 8));  // -1
        System.out.println(binarySearch(data, 1));  // 0
        System.out.println(binarySearch(data, 13)); // 6
    }
}

進階變體：左邊界/右邊界查找 (處理重複元素)

當陣列含重複元素，標準版返回任意一個匹配索引。實際常需：

• 左邊界：第一個 >= target 的位置 (lower_bound)
• 右邊界：最後一個 <= target 的位置 (upper_bound - 1)

左邊界查找 (第一個 ≥ target)

/**
 * 查找左邊界：返回第一個 >= target 的索引
 * 若所有元素 < target，返回 arr.length (插入位置)
 * 等價於 C++ lower_bound
 */
public static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length; // 開區間 [left, right)

    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid; // arr[mid] >= target，收縮右邊界
        }
    }
    return left; // left == right
}

右邊界查找 (最後一個 ≤ target)

/**
 * 查找右邊界：返回最後一個 <= target 的索引
 * 若所有元素 > target，返回 -1
 * 等價於 C++ upper_bound - 1
 */
public static int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length; // 開區間 [left, right)

    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] <= target) {
            left = mid + 1; // arr[mid] <= target，收縮左邊界
        } else {
            right = mid;
        }
    }
    return left - 1; // left 是第一個 > target 的位置
}

區間查找應用：統計目標值出現次數

public static int countOccurrences(int[] arr, int target) {
    int left = lowerBound(arr, target);
    int right = upperBound(arr, target);
    if (left <= right && left < arr.length && arr[left] == target) {
        return right - left + 1;
    }
    return 0;
}

// 範圍計數：統計 [L, R] 區間內元素個數
public static int countRange(int[] arr, int L, int R) {
    int left = lowerBound(arr, L);
    int right = upperBound(arr, R);
    return Math.max(0, right - left + 1);
}

Java 內建 API 對比

// 解碼 Arrays.binarySearch 返回值
int idx = Arrays.binarySearch(arr, target);
if (idx >= 0) {
    System.out.println("找到，索引: " + idx);
} else {
    int insertPos = -idx - 1;
    System.out.println("未找到，應插入位置: " + insertPos);
}

遞迴版實現 (教學用)

public static int binarySearchRecursive(int[] arr, int target) {
    return binarySearchRecursive(arr, target, 0, arr.length - 1);
}

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

泛型化支援 Comparable

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

關鍵細節與避坑指南

1. 中點計算防溢位：mid = left + ((right - left) >> 1)，不可用 (left + right) / 2
2. 迴圈條件：閉區間用 left <= right，開區間用 left < right
3. 邊界收縮：left = mid + 1 / right = mid - 1 (閉區間)；left = mid + 1 / right = mid (開區間)
4. 返回值語義：明確定義找到/未找到/插入位置的返回約定
5. 前置條件檢查：陣列非空、已排序 (可加 assert isSorted(arr))

實戰應用場景

• 資料庫索引查找 (B+ 樹本質是多路二分)
• 版本號查找：第一個壞版本 (LeetCode 278)
• 平方根計算：sqrt(x) 二分整數解
• 分頁查詢游標：WHERE id > last_id ORDER BY id LIMIT n
• 記憶體對齊/區塊分配：Buddy System 分配器