Java 演算法：二分搜尋法原理、邊界處理與完整實作

Java 演算法：二分搜尋法原理、邊界處理與完整實作

二分搜尋是查找有序陣列中目標值的高效演算法，時間複雜度 O(log n)。本文從邏輯推導、常見陷阱（死迴圈、索引越界）、完整 Java/PHP 實作三方面，帶你徹底掌握。

核心前提

陣列必須已排序（升序），否則二分搜尋邏輯不成立。

演算法推導步驟

1. 定義三個指標

int min = 0;
int max = arr.length - 1;
int mid = (min + max) / 2;

2. 迴圈條件：當中間值不等於目標值時繼續

while (arr[mid] != key) {
    if (key < arr[mid]) {
        max = mid - 1;  // 目標在左半部
    } else { // arr[mid] < key
        min = mid + 1;  // 目標在右半部
    }
    mid = (min + max) / 2; // 重新計算中間
}

3. 關鍵修正：避免找不到時陷入死迴圈

若目標不存在，min 會超過 max（錯位），必須加入終止條件：

while (arr[mid] != key) {
    if (key < arr[mid]) {
        max = mid - 1;
    } else {
        min = mid + 1;
    }
    if (min > max) return -1; // 找不到
    mid = (min + max) / 2;
}
return mid;

完整 Java 實作

public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] arr = {1, 4, 6, 7, 8, 9};
        System.out.println("線性搜尋 7 索引: " + linearSearch(arr, 7)); // 3
        System.out.println("二分搜尋 7 索引: " + binarySearch(arr, 7)); // 3
        System.out.println("二分搜尋 5 索引: " + binarySearch(arr, 5)); // -1
    }

    // 二分搜尋（回傳索引，找不到回傳 -1）
    public static int binarySearch(int[] arr, int key) {
        int min = 0, max = arr.length - 1, mid = (min + max) / 2;
        while (arr[mid] != key) {
            if (key < arr[mid]) max = mid - 1;
            else min = mid + 1;
            if (min > max) return -1;
            mid = (min + max) / 2;
        }
        return mid;
    }

    // 線性搜尋（對照參考）
    public static int linearSearch(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) return i;
        }
        return -1;
    }
}

PHP 版本對照

<?php
class ArrayDemo {
    public static function main() {
        $arr = array(1, 4, 6, 7, 8, 9);
        echo "線性搜尋 7 索引: " . self::linearSearch($arr, 7) . "\n"; // 3
        echo "二分搜尋 7 索引: " . self::binarySearch($arr, 7) . "\n"; // 3
        echo "二分搜尋 5 索引: " . self::binarySearch($arr, 5) . "\n"; // -1
    }

    public static function binarySearch($arr, $key) {
        $min = 0; $max = count($arr) - 1; $mid = (int)(($min + $max) / 2);
        while ($arr[$mid] != $key) {
            if ($key < $arr[$mid]) $max = $mid - 1;
            else $min = $mid + 1;
            if ($min > $max) return -1;
            $mid = (int)(($min + $max) / 2);
        }
        return $mid;
    }

    public static function linearSearch($arr, $key) {
        for ($i = 0; $i < count($arr); $i++) {
            if ($arr[$i] == $key) return $i;
        }
        return -1;
    }
}
ArrayDemo::main();
?>

常見錯誤與避坑指南

實務建議

• 生產環境請直接使用 Arrays.binarySearch() 或 Collections.binarySearch()，經過嚴格測試並支援泛型、比較器。
• 若需「第一個大於等於目標值的索引」（下界），可修改邏輯回傳 min 而非 -1。
• 理解二分邊界收斂邏輯，是解決「搜尋答案空間」類題目（如 LeetCode 找峰值、最小化最大值）的基礎。