Collections.binarySearch()用于在排序列表中高效查找目标值，时间复杂度为O(log n)，使用前必须确保列表已排序，否则结果不可预测；该方法有两个重载版本，分别适用于实现Comparable接口的元素和自定义Comparator比较规则的情况，查找成功返回索引，失败返回-(插入点)-1，可用于优化大型有序数据的搜索性能。
二分查找，简单来说，就是在排序好的列表中快速找到目标值的位置。Java 的
Collections.binarySearch()方法就是干这个的。它比你自己手写二分查找要方便，而且经过了优化，效率更高。
Collections.binarySearch() 方法的使用其实挺直接的，但有些细节要注意，不然可能会踩坑。
如何正确使用 Collections.binarySearch()
Collections.binarySearch()有两个主要的重载方法：
-
binarySearch(List> list, T key)
：这个方法用于查找实现了Comparable
接口的元素列表。也就是说，列表中的元素本身就应该知道如何比较大小。立即学习“Java免费学习笔记（深入）”；
binarySearch(List list, T key, Comparator c)
：这个方法更灵活，你可以传入一个Comparator
对象来定义元素之间的比较规则。这在你需要按照非自然顺序比较元素时非常有用。
使用示例（Comparable 接口）：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BinarySearchExample {
public static void main(String[] args) {
List numbers = new ArrayList<>();
numbers.add(2);
numbers.add(5);
numbers.add(8);
numbers.add(11);
numbers.add(12);
int index = Collections.binarySearch(numbers, 11);
System.out.println("Index of 11: " + index); // Output: Index of 11: 3
int notFoundIndex = Collections.binarySearch(numbers, 7);
System.out.println("Index of 7: " + notFoundIndex); // Output: Index of 7: -3
}
} 使用示例（Comparator 接口）：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class BinarySearchExample {
public static void main(String[] args) {
List names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");
names.add("David");
// 按照字符串长度排序
Comparator lengthComparator = Comparator.comparingInt(String::length);
Collections.sort(names, lengthComparator); // 先排序
int index = Collections.binarySearch(names, "Bob", lengthComparator);
System.out.println("Index of Bob: " + index);
}
} 返回值：
- 如果找到目标值，返回其在列表中的索引。
- 如果没找到，返回
-(insertion point) - 1
。这个 insertion point 是指如果目标值应该插入到列表中的哪个位置才能保持排序。这个返回值有点反直觉，但它能告诉你如果目标值存在，它应该在哪里。
为什么一定要先排序？
二分查找的核心前提是列表必须是排序好的。如果列表没有排序，
binarySearch()的结果是不可预测的，很可能返回错误的结果。这就像在一堆乱七八糟的书里找一本特定的书，效率肯定很低，而且很可能找不到。
性能怎么样？时间复杂度是多少？
Collections.binarySearch()的时间复杂度是 O(log n)，其中 n 是列表的大小。这意味着随着列表的增大，查找时间只会以对数级别增长。相比于线性查找的 O(n) 时间复杂度，二分查找在大型列表中的效率优势非常明显。
如果列表中有重复元素怎么办？
如果列表中有重复的元素，
binarySearch()并不保证返回哪个重复元素的索引。它可能会返回任何一个重复元素的索引。如果你需要找到所有重复元素的索引，或者第一个/最后一个重复元素的索引，你可能需要自己实现更复杂的查找逻辑。
Collections.binarySearch() 和数组的 Arrays.binarySearch() 有什么区别？
Collections.binarySearch()用于
List接口的实现类，比如
ArrayList和
LinkedList。而
Arrays.binarySearch()用于数组。它们的功能类似，但适用的数据结构不同。
实际应用场景有哪些？
- 搜索排序好的数据： 在数据库索引、字典查找等场景中，二分查找可以快速定位到目标数据。
-
算法题： 很多算法题都涉及到在排序数组中查找元素，
binarySearch()
可以作为一个方便的工具。 - 优化查找性能： 当你需要频繁在一个大型排序列表中查找元素时，使用二分查找可以显著提高性能。
如何处理可能出现的异常？
Collections.binarySearch()本身不会抛出异常，但你需要确保传入的参数是有效的。例如，如果你使用了带
Comparator的重载方法，你需要确保
Comparator对象能够正确比较列表中的元素。
除了 Collections.binarySearch() 还有其他选择吗？
当然，你可以自己实现二分查找算法。但
Collections.binarySearch()已经经过了优化，通常情况下，直接使用它就足够了。除非你有特殊的需求，比如需要定制查找逻辑或者处理非常特殊的数据结构。
总的来说，
Collections.binarySearch()是一个非常实用的工具，可以帮助你在排序列表中快速查找元素。掌握它的使用方法和注意事项，可以让你在 Java 开发中更加高效。
