Java 二分查找法實現：有序數組高效查找演算法與兩種寫法對比

Java 二分查找法實現

前提：陣列**已排序**。透過不斷縮小查找區間 [min, max]，時間複雜度 O(log n)。

版本一：標準 while 迴圈

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]) min = mid + 1;
        else if (key < arr[mid]) max = mid - 1;
        if (max < min) return -1; // 未找到
        mid = (min + max) / 2;
    }
    return mid;
}

版本二：更簡潔的邊界控制

public static int binarySearch2(int[] arr, int key) {
    int min = 0, max = arr.length - 1, mid;
    while (min <= max) {
        mid = (min + max) / 2;
        if (key > arr[mid]) min = mid + 1;
        else if (key < arr[mid]) max = mid - 1;
        else return mid;
    }
    return -1;
}

完整測試類別

package com.db2;
import java.util.Arrays;

public class Demo4 {
    public static void main(String[] args) {
        int[] arr = {3,1,8,2,9,100,33,22,11,18,14,17,15,3};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("index=" + binarySearch2(arr, 11));
    }
    // ... 兩個 binarySearch 方法置於此 ...
}

注意事項

• 陣列必須有序，否則結果不可預期。
• mid = (min + max) / 2 可能溢位，生產環境建議 mid = min + (max - min) / 2 或 (min + max) >>> 1。
• 若有重複元素，回傳任一匹配索引；需首尾索引可改用 Arrays.binarySearch 或自行擴展。