Collections.binarySearch方法解析_技术教程_奈瑶·映南科技互联网学院

Collections.binarySearch通过二分查找在已排序列表中高效定位元素，时间复杂度O(log n)，适用于自然或自定义排序的列表，返回索引或插入点负值，广泛用于性能敏感场景如数据库索引和游戏开发。

Collections.binarySearch

方法本质上是在已排序的列表中高效地查找特定元素的索引。它利用二分查找算法，大幅减少了搜索时间，尤其是在处理大型数据集时。

Collections.binarySearch(list, key)

Collections.binarySearch 的优势与局限

Collections.binarySearch

的主要优势在于其效率。对于已经排序的列表，它的时间复杂度为 O(log n)，这意味着搜索时间随着列表大小的增长而呈对数级增长。相比于线性搜索的 O(n) 复杂度，优势非常明显。

但它的局限性也很明显。首先，

binarySearch

只能应用于已排序的列表。如果列表未排序，结果将是不可预测的。其次，如果列表中存在多个相同的元素，

binarySearch

不保证返回哪个元素的索引。

如何确保 Collections.binarySearch 正常工作？

确保

Collections.binarySearch

正常工作的关键在于，输入的列表必须已经按照自然顺序或指定的比较器进行排序。如果使用自然顺序，列表中的元素必须

实现

Comparable

接口。如果使用自定义比较器，则需要提供一个

Comparator

实例。

例如，对于整数列表，可以直接使用

Collections.sort(list)

进行排序。对于自定义对象列表，需要实现

Comparable

接口或提供一个

Comparator

。

Collections.binarySearch 返回值的意义

Collections.binarySearch

的返回值有三种情况：

如果找到目标元素，则返回该元素在列表中的索引（从 0 开始）。
如果未找到目标元素，则返回一个负数。这个负数表示如果目标元素应该插入到列表中以保持排序，则插入点的索引的负值减 1。例如，如果返回 -5，表示目标元素应该插入到索引 4 的位置。
如果列表为空，则返回 -1。

Collections.binarySearch 与手动二分查找的比较

虽然

Collections.binarySearch

提供了方便的二分查找实现，但手动实现二分查找可以提供更大的灵活性。例如，可以自定义查找逻辑，处理特定的边界情况，或者在找到目标元素后执行其他操作。

手动实现二分查找的一个简单示例：

public static int binarySearch(List list, int key) {
    int low = 0;
    int high = list.size() - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1; // 防止溢出
        int midVal = list.get(mid);

        if (midVal < key) {
            low = mid + 1;
        } else if (midVal > key) {
            high = mid - 1;
        } else {
            return mid; // key found
        }
    }
    return -(low + 1);  // key not found.
}

这个手动实现的版本与