集合查找：binarySearch 和其他方法

binarySearch：二分查找的前提条件

binarySearch 是二分查找，必须先对列表排序才能使用。

List<Integer> list = Arrays.asList(1, 3, 5, 7, 9, 11);

// ✅ 有序列表，binarySearch 正确
int index = Collections.binarySearch(list, 7);
System.out.println(index); // 3

---

返回值规则

binarySearch 的返回值规则很有意思：

List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);

int index1 = Collections.binarySearch(list, 7); // 3（找到了，返回索引）
int index2 = Collections.binarySearch(list, 6); // -4（没找到，返回 -插入点-1）

没找到时返回 -插入点 - 1，为什么要减 1？

• 防止插入点为 0 时返回 0（和「在索引 0 找到」混淆）
• -(-3) - 1 = 2 意味着应该插在索引 2

---

带比较器的 binarySearch

降序查找

List<String> list = Arrays.asList("c", "b", "a");

// 按降序排列
Collections.sort(list, Collections.reverseOrder());
// ["c", "b", "a"]

// 查找时也要用降序比较器
int index = Collections.binarySearch(list, "b", Collections.reverseOrder());

自定义对象查找

List<Student> students = Arrays.asList(
    new Student("张三", 85),
    new Student("李四", 92),
    new Student("王五", 78)
);

// 按分数排序
students.sort(Comparator.comparingInt(Student::getScore));

// 查找时用相同的比较器
int index = Collections.binarySearch(students,
    new Student("", 92),
    Comparator.comparingInt(Student::getScore)
);

---

Arrays.binarySearch

基本用法

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

// 先排序
Arrays.sort(arr);

// 再二分查找
int index = Arrays.binarySearch(arr, 7);
System.out.println(index); // 3

带比较器

String[] arr = {"apple", "banana", "cherry"};
int index = Arrays.binarySearch(arr, "banana", String::compareTo);

部分查找

// 二分查找 数组的 [fromIndex, toIndex) 区间
int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
Arrays.sort(arr, 2, 7); // 排序 arr[2]~arr[6]
int index = Arrays.binarySearch(arr, 2, 7, 5); // 在 arr[2,7) 中找 5

---

indexOfSubList / lastIndexOfSubList

子列表查找

List<String> list = Arrays.asList("a", "b", "c", "a", "b", "a");
List<String> sub = Arrays.asList("a", "b");

int first = Collections.indexOfSubList(list, sub);   // 0
int last = Collections.lastIndexOfSubList(list, sub); // 3

---

常见错误

错误 1：列表无序就二分查找

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5, 9);

// ❌ 无序列表，二分查找结果不可靠
int index = Collections.binarySearch(list, 4);
System.out.println(index); // 可能是负数（结果不确定）

// ✅ 先排序
Collections.sort(list);
index = Collections.binarySearch(list, 4);

错误 2：比较器不一致

List<String> list = Arrays.asList("a", "B", "c");

// 排序用不区分大小写
Collections.sort(list, String.CASE_INSENSITIVE_ORDER); // [a, B, c]

// ❌ 查找用自然顺序比较器（不一致）
int index = Collections.binarySearch(list, "b");

// ✅ 查找用相同的比较器
int index2 = Collections.binarySearch(list, "b", String.CASE_INSENSITIVE_ORDER);

---

总结

要点	说明
必须有序	binarySearch 必须在排序后使用
返回值	找到返回索引，没找到返回 -插入点-1
比较器	排序和查找必须用相同的比较器
适用	大量查找，已排序的集合

一句话：binarySearch 是「已排序集合的快速查找器」——先排序，再二分。

---

相关链接

• 集合排序
• 二分查找算法