Java Collections.binarySearch 正確用法與常見坑

問題場景

開發者直接對未排序的 List 調用 Collections.binarySearch()，導致返回負數索引（如 -1、-2），誤以為方法故障。實際上二分查找**前提條件是列表必須已按自然順序或指定 Comparator 排序**。

錯誤代碼示例

List<Integer> list = new ArrayList<>();
list.add(5);
list.add(2);
list.add(8);
list.add(1);
// 未排序直接查找
int idx = Collections.binarySearch(list, 2); // 返回 -2 (插入點 -1 -1)
System.out.println(idx); // 輸出負數，非預期索引

正確用法

List<Integer> list = new ArrayList<>();
list.add(5);
list.add(2);
list.add(8);
list.add(1);

// 1. 先排序
Collections.sort(list); // [1, 2, 5, 8]

// 2. 再二分查找
int idx = Collections.binarySearch(list, 2); // 返回 1 (正確索引)
System.out.println("元素 2 的索引: " + idx);

// 3. 若使用自定義比較器，查找時必須傳入同一比較器
Comparator<Integer> cmp = (a, b) -> b - a; // 降序
Collections.sort(list, cmp); // [8, 5, 2, 1]
idx = Collections.binarySearch(list, 2, cmp); // 返回 2

返回值規則詳解

• 找到元素：返回元素索引（0-based），若有重複元素，**不保證返回第一個**。
• 未找到：返回 -(插入點) - 1。插入點是為保持有序而應插入的位置。
  例如列表 [10, 20, 30] 查找 15 → 插入點 1 → 返回 -2。

最佳實踐建議

1. **永遠先調用 Collections.sort()**，或確保列表構建時已有序。
2. 若列表頻繁修改，考慮使用 TreeSet 或 ConcurrentSkipListSet 維持有序性。
3. 對大數據量（>10⁶），二分查找 O(log n) 優於線性搜索 O(n)，但排序成本 O(n log n) 需權衡。
4. 自定義對象需實現 Comparable 或提供 Comparator，並保證 compareTo 與 equals 一致。

源碼級理解

JDK 實現中 binarySearch 會判斷列表是否實現 RandomAccess（如 ArrayList），若否則退化為迭代器二分（O(n) 訪問），效率大幅下降。因此**優先使用 ArrayList 等隨機訪問列表**。