Java 實作二分搜尋演算法完整教學

什麼是二分搜尋

又稱折半搜尋，針對已排序序列，每次以中點比較，將搜尋範圍縮減一半，時間複雜度 O(log n)。

前提條件

• 序列必須有序（升序或降序）。
• 支援隨機存取（陣列或 List）。

優缺點

適用場景：不常變動但頻繁查詢的有序列表。

演算法步驟

1. 設定 min=0, max=length-1。
2. 計算 mid = (min + max) / 2。
3. 比較 arr[mid] 與目標值：
   相等 → 回傳索引；
   小於 → min = mid + 1；
   大於 → max = mid - 1。
4. 重複直到 min > max（查無此值，回傳 -1）。

Java 實作

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        if (arr == null) return -1;
        int min = 0, max = arr.length - 1;
        while (min <= max) {
            int mid = (min + max) >>> 1; // 無符號右移避免溢位
            if (arr[mid] < target) min = mid + 1;
            else if (arr[mid] > target) max = mid - 1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5, 6, 7, 8, 9, 23, 34};
        System.out.println(binarySearch(arr, 5));   // 3
        System.out.println(binarySearch(arr, 23));  // 8
        System.out.println(binarySearch(arr, 0));   // -1
        System.out.println(binarySearch(arr, 35));  // -1
    }
}

關鍵細節

• 使用 >>> 1 而非 / 2 避免 min+max 溢位（雖 Java int 正數相加不會溢位為負，但屬良好習慣）。
• 迴圈條件 min <= max 確保單一元素也能檢查。
• 若需查找插入位置（lower/upper bound），可調整回傳邏輯。