Java中Collections.binarySearch集合查找有哪些技巧？

Java标准库中的Collections.binarySearch是一种基于二分查找的集合检索工具，调用时最容易忽略的前提是目标集合必须有序。如果直接传入一个乱序的List，即使元素确实存在，也可能返回负数，让人误以为没有找到。

这篇文章会从排序前提、比较器用法、返回值解读、性能对比和源码实现几个方向，把Collections.binarySearch的查找技巧讲清楚。

排序是二分查找的前置条件

二分查找的核心思想是每次与区间中间元素比较，如果目标值小于中间元素，就丢弃右半部分；如果大于中间元素，就丢弃左半部分。这个逻辑能够成立的基础，是集合已经按照相同顺序排好。对一个乱序的List调用binarySearch，程序并不会自动排序，也不会报错，但返回结果与随机猜测差不多。

因此，在调用binarySearch之前，必须先使用Collections.sort或List.sort完成排序。下面的例子展示了标准用法：先向ArrayList添加字符串，排序后再执行查找。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchDemo {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Tom");
        names.add("Alice");
        names.add("Bob");
        names.add("Cindy");

        // 必须先排序，否则二分查找结果不可靠
        Collections.sort(names);
        System.out.println("排序后: " + names);

        int index = Collections.binarySearch(names, "Bob");
        System.out.println("Bob 的下标: " + index);
    }
}

运行这段代码，控制台会输出排序后的列表以及Bob的索引。由于排序后列表为Alice、Bob、Cindy、Tom，因此查找Bob会返回1。需要注意的是，Collections.sort默认按照元素的自然顺序排序，也就是String实现Comparable接口后的字典序。如果业务中的排序规则不是自然顺序，那么binarySearch同样需要知道这个规则，这就引出了比较器的使用。

用Comparator处理自定义对象和降序场景

对于自定义对象，例如一个包含姓名和年龄的Person类，如果直接调用Collections.binarySearch而不传入比较器，会要求Person类实现Comparable接口。有些场景下，我们希望按照年龄排序，又不想把排序字段写死到类里，这时可以传入一个Comparator。

另一个容易出错的地方是降序查找。如果列表按照降序排列，但查找时使用自然顺序或错误的比较器，二分逻辑会完全失效。解决办法很简单：排序时和查找时使用同一个比较器。下面示例先按年龄升序排序并查找，然后按姓名降序排序并查找。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + ":" + age;
    }
}

public class ComparatorSearchDemo {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>();
        people.add(new Person("Tom", 25));
        people.add(new Person("Alice", 30));
        people.add(new Person("Bob", 20));

        Comparator<Person> byAge = Comparator.comparingInt(p -> p.age);
        people.sort(byAge);
        int ageIndex = Collections.binarySearch(people, new Person("", 25), byAge);
        System.out.println("年龄25的下标: " + ageIndex);

        Comparator<Person> byNameDesc = Comparator.comparing((Person p) -> p.name).reversed();
        people.sort(byNameDesc);
        int nameIndex = Collections.binarySearch(people, new Person("Tom", 0), byNameDesc);
        System.out.println("Tom 在降序姓名列表中的下标: " + nameIndex);
    }
}

这里查找年龄时，待查找对象的姓名并不重要，因为比较器只读取age字段。查找姓名时，同理只比较name。可见，Comparator不仅让二分查找适用于任意对象，还能轻松支持降序、组合排序等复杂规则。只要保证排序和查找使用同一个比较器，结果就是稳定的。

如果排序时使用Comparator.reverseOrder()，查找时也必须传入相同的反转比较器，不能只传null或省略比较器。

返回值负数并不只是“没找到”

Collections.binarySearch的返回值设计得比较特殊：找到元素时返回键所在的索引；找不到元素时返回-(insertion point) - 1。所谓插入点，就是如果要把这个元素插入到有序列表中，它应该所在的位置。这个负值不能直接当作索引使用，但可以还原出插入位置，方法是对返回值取负再减一，或者使用-index - 1。

例如列表为[10, 20, 30]，查找25会返回-3，因为25的插入点是索引2（在20和30之间），计算方式为-(2)-1=-3。如果看到负数就以为只是查找失败，会浪费二分查找提供的定位能力。借助插入点，可以快速完成有序插入操作。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ReturnValueDemo {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(10);
        nums.add(20);
        nums.add(30);

        int index = Collections.binarySearch(nums, 25);
        if (index >= 0) {
            System.out.println("找到元素，索引为 " + index);
        } else {
            int insertPoint = -index - 1;
            System.out.println("未找到，插入点为 " + insertPoint);
            nums.add(insertPoint, 25);
        }

        System.out.println(nums);
    }
}

输出结果是[10, 20, 25, 30]。代码中先根据负数返回值计算出插入点，再把25插入到该位置，列表依然保持有序。这也是binarySearch返回值的重要技巧：查不到不代表没有价值，负数中携带了有序插入的位置信息。

当然，必须再次强调，这个插入点只有在列表有序时才有意义。乱序列表的返回值既不能反映索引，也不能反映插入点。

binarySearch与contains、indexOf的性能差异

在Java集合中，查找元素还可以使用List.contains或List.indexOf。这些方法内部走的是线性遍历，从头到尾逐个比较，时间复杂度为O(n)。而Collections.binarySearch使用二分查找，时间复杂度为O(log n)。当数据量增长时，差距是指数级的。例如在包含一百万个元素的列表中，线性查找平均需要五十万次比较，而二分查找最多只需要约二十次比较。

但二分查找并不是没有代价。它要求列表预先排序，排序本身通常需要O(n log n)时间。如果列表只查找一次，排序加查找的总成本可能高于直接线性扫描。因此，binarySearch更适合“排序一次、多次查找”的场景。比如系统启动时加载一份配置列表并排序，后续有大量查询请求命中该列表，这时候性能收益非常明显。

还有一个细节：Collections.binarySearch适用于List接口，底层通常是ArrayList或LinkedList。但二分查找需要根据索引快速访问中间元素，所以对ArrayList来说它的get(int index)是O(1)，性能很好；对LinkedList来说get(int index)是O(n)，二分查找的优势会被抵消，甚至比线性查找还慢。因此，实际项目中如果要对集合频繁执行二分查找，应优先选择ArrayList。

从源码看二分查找的边界处理

Collections.binarySearch的内部实现并不复杂，但它对索引的计算非常严谨。核心循环大致如下：定义low和high两个边界，每次计算中间位置mid = (low + high) >>> 1，这里使用无符号右移，可以避免low + high溢出的问题。接着用比较器比较中间元素与目标键，如果中间元素小于键，就把low移动到mid + 1；如果中间元素大于键，就把high移动到mid - 1；相等则直接返回mid。

如果循环结束还没有找到，返回-(low + 1)。这里的low恰好是插入点，所以源码直接返回-(low + 1)。理解这一点后，再看返回值负数就能明白设计意图。下面是一段简化版的二分查找实现，帮助理解边界变化。

import java.util.Comparator;
import java.util.List;

public class SimpleBinarySearch {
    public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
        int low = 0;
        int high = list.size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            T midVal = list.get(mid);
            int cmp = c.compare(midVal, key);

            if (cmp < 0) {
                low = mid + 1;
            } else if (cmp > 0) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -(low + 1);
    }
}

这段代码展示了二分查找的经典边界处理。可以看到，mid使用>>> 1而不是/ 2，是为了在low + high结果很大时避免有符号溢出问题。当low大于high时，循环退出，此时low就是元素应该插入的位置。这也是为什么找不到时返回值是-(low + 1)的原因。

掌握了这些实现细节，再回过头看Collections.binarySearch的日常使用，就会对“必须有序”“比较器必须一致”“负数包含插入点”等要求有更清晰的理解。

Java Collections.binarySearch二分查找集合查找修改时间：2026-10-02 22:48:57