Java 二分查找算法實現與性能優化：遞歸 vs 迭代深度對比

前言

二分查找是計算機科學中最基礎、最高效的查找算法之一，**前提：數據必須有序 (升序/降序)**。時間複雜度 O(log n)，空間複雜度遞歸 O(log n)、迭代 O(1)。本文提供標準實現、邊界條件處理、遞歸與迭代深度對比、以及避免溢出的最佳實踐。

核心前提

• 數組/列表**必須已排序** (升序)。
• 支持隨機訪問 (數組、ArrayList)，不適用於鏈表。
• 查找目標：確定元素是否存在、返回索引、或插入位置。

標準實現：迭代版 (生產首選)

/**
 * 標準二分查找 (迭代版)
 * @param arr 升序數組
 * @param target 目標值
 * @return 找到返回索引 (0-based)，未找到返回 -1
 */
public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1; // 閉區間 [left, right]
    
    while (left <= right) { // 區間非空
        // 防溢出寫法：left + (right - left) / 2
        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 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;
    else if (arr[mid] < target) 
        return binarySearchRecursive(arr, target, mid + 1, right);
    else 
        return binarySearchRecursive(arr, target, left, mid - 1);
}

關鍵細節深度解析

1. 中間索引計算：防止整數溢出

2. 邊界條件：閉區間 vs 半開區間

• 閉區間 [left, right]：while (left <= right)，更新 left = mid + 1 / right = mid - 1。**最直觀，推薦**。
• 半開區間 [left, right)：while (left < right)，更新 left = mid + 1 / right = mid。需注意終止條件與返回值語義。

3. 變體：查找第一個/最後一個等於目標值 (重複元素)

// 查找第一個 >= target (下界 lower_bound)
public static int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length; // 半開區間 [left, right)
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left; // 返回插入位置 / 第一個 >= target 的索引
}

// 查找第一個 > target (上界 upper_bound)
public static int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left; // 返回第一個 > target 的索引
}

// 統計目標值出現次數
public static int countTarget(int[] arr, int target) {
    return upperBound(arr, target) - lowerBound(arr, target);
}

遞歸 vs 迭代：全維度對比

Java 標準庫實現參考

• Arrays.binarySearch()：原生優化、支持所有基本類型數組、物件數組 (需 Comparable/Comparator)。**首選標準庫**。
• Collections.binarySearch()：List 版本，隨機訪問列表 (ArrayList) 效率高，鏈表會退化為線性。

性能實測 (1000 萬有序整數，查找存在/不存在)

總結與最佳實踐

1. 生產代碼首選 Arrays.binarySearch()，標準庫經過極致優化、測試完備。
2. 手寫必用迭代版，配合 left + (right - left) / 2 防溢出，閉區間邏輯最清晰。
3. 掌握 lowerBound/upperBound 變體，解決「插入位置、範圍查詢、重複元素統計」等實戰問題。
4. 前提檢查：數據無序 → 先排序 (O(n log n)) 或用 HashSet (O(1) 查找，空間換時間)。
5. 泛型化：配合 Comparator 支持任意類型有序集合查找。

二分查找是「簡單而不易」的經典算法。**邊界條件、溢出防護、變體靈活運用** 是區分初級與資深工程師的分水嶺。將標準庫與手寫迭代版納入工具箱，讓 O(log n) 查找成為你處理有序數據的利器。