java二分搜索要注意什么

在 Java 中使用**二分搜索（Binary Search）**时，有几个关键点和常见坑需要注意，尤其是用 Arrays.binarySearch 或自己手写实现时。

一、前提条件（最重要）

数组必须是有序的

• 升序或降序都可，但必须“已排序”
• 如果数组无序，二分搜索结果不可信

int[] arr = {1, 3, 5, 7, 9}; // OK

二、使用 Arrays.binarySearch 的注意事项

1. 返回值含义

int index = Arrays.binarySearch(arr, key);

• index >= 0：找到元素，返回索引
• index < 0：未找到
  • 插入位置为：-(index + 1)

int[] arr = {1, 3, 5};
int i = Arrays.binarySearch(arr, 4); // i = -3
// 插入位置是 2

2. 对象数组要正确实现 Comparable

如果是对象数组：

Arrays.binarySearch(list, obj);

• 对象必须实现 Comparable
• 或传入 Comparator

Arrays.binarySearch(users, user, Comparator.comparing(User::getId));

3. 自定义比较器时顺序要一致

如果排序用了 Comparator，二分也必须用同一个 Comparator

❌ 错误示例：

Arrays.sort(list, Comparator.reverseOrder());
Arrays.binarySearch(list, x); // 可能出错

✅ 正确：

Arrays.binarySearch(list, x, Comparator.reverseOrder());

三、手写二分搜索常见问题

1. 循环条件

常用写法：

while (left <= right)

而不是：

while (left < right) // 容易漏元素

2. 防溢出

int mid = left + (right - left) / 2;

不要用：

int mid = (left + right) / 2; // 可能溢出

3. 边界更新

if (arr[mid] < target) {
    left = mid + 1;
} else {
    right = mid - 1;
}

写错容易死循环或漏解。

4. 重复元素问题

标准二分只找一个位置，不保证是第一个或最后一个

• 找第一个 ≥ target：左边界二分
• 找最后一个 ≤ target：右边界二分

四、常见错误总结

五、什么时候不该用二分

• 数据量很小（< 20）
• 频繁插入删除（用 TreeSet / TreeMap）
• 无序且不能排序

如果你愿意，我可以：

• 给你一个标准二分模板
• 讲 左边界 / 右边界二分
• 或帮你改一段二分代码