当前位置：首页 > 文章列表 > 文章 > java教程 > 使用 Collections.binarySearch() 实现对数查找方法

使用 Collections.binarySearch() 实现对数查找方法

2026-05-22 19:00:34 0浏览收藏

Java 的 Collections.binarySearch() 是专为已排序 List 设计的高效对数时间（O(log n)）查找工具，但其正确性完全依赖于列表严格升序（或按同一 Comparator 有序）的前提——若未排序，结果将不可预测；它返回非负索引表示成功找到元素，负值则隐含插入位置信息，适用于高频查询场景；需注意优先选用 ArrayList 而非 LinkedList 以避免随机访问开销，且排序只需一次，后续可反复调用，是兼顾性能与简洁性的关键实践。

怎么利用 Collections.binarySearch() 在已经排序的 List 中实现对数时间复杂度的查找

Collections.binarySearch() 是 Java 提供的、专为已排序 List 设计的对数时间（O(log n)）查找工具。它底层调用的是 Arrays.binarySearch() 的适配逻辑，要求列表必须**严格升序排列**（或按指定 Comparator 有序），否则结果未定义。

前提：确保 List 已正确排序

二分查找不检查顺序，只依赖索引中点比较。若列表无序，返回值不可靠（可能负数，也可能碰巧返回正索引但实际查不到）。

升序自然排序：Collections.sort(list)（仅需排一次，后续可反复调用 binarySearch）
自定义顺序：用 Collections.sort(list, comparator) 排序，并在 binarySearch 中传入**同一个 comparator**
注意：ArrayList 和 LinkedList 都支持，但 LinkedList 的随机访问是 O(n)，会拖慢二分过程；推荐用 ArrayList

基本用法与返回值含义

方法签名：

public static int binarySearch(List> list, T key)

或带比较器的版本：

public static int binarySearch(List list, T key, Comparator c)

返回值：

≥ 0：找到元素，返回其**索引位置**（唯一匹配时返回该位置；有重复时返回任意一个匹配索引，不保证是第一个或最后一个）
＜ 0：未找到，返回值为 -(insertionPoint) - 1，其中 insertionPoint 是保持排序所需插入的位置（即第一个 ≥ key 的索引）

实用技巧与常见处理

利用返回值可快速实现多种需求：

判断是否存在：binarySearch(list, key) >= 0
获取插入位置（用于维护有序性）：int pos = -(result + 1)（当 result
查找重复元素的左边界？——binarySearch 不直接支持，需配合手动二分或改用 Arrays.binarySearch + list.toArray() 后处理
避免自动装箱陷阱：对基本类型包装类（如 Integer），确保比较逻辑一致（例如不要混用 new Integer(1) 和 Integer.valueOf(1) 在自定义 comparator 中）

完整示例（升序 + 自定义 Comparator）

```java
ArrayList words = new ArrayList<>(Arrays.asList("apple", "banana", "cherry", "date"));
Collections.sort(words); // 升序
int idx = Collections.binarySearch(words, "cherry"); // 返回 2

// 按长度排序并查找
Collections.sort(words, Comparator.comparing(String::length));
idx = Collections.binarySearch(words, "fig", Comparator.comparing(String::length)); // 返回 0（"fig" 长度为 3，插在 "apple" 前）
```

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《使用 Collections.binarySearch() 实现对数查找方法》文章吧，也可关注golang学习网公众号了解相关技术文章。