Java中的Collections.binarySearch()及其示例

在Java中，对于已排序的集合可以使用Collections类中的binarySearch()方法来查找特定元素的索引。该方法使用二分搜索算法实现，其时间复杂度为O(log n)，比线性搜索更加高效。

用法举例

下面是一个使用Collections.binarySearch()方法来查找元素索引的示例。

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

public class BinarySearchExample {
    public static void main(String[] args) {
        // 创建一个已排序的整数列表
        List<Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        numbers.add(50);

        // 查找元素的索引
        int index = Collections.binarySearch(numbers, 40);

        // 输出结果
        if (index >= 0) {
            System.out.println("元素 40 在列表中的索引为：" + index);
        }
        else {
            System.out.println("元素 40 不存在于列表中。");
        }
    }
}

上述示例会输出以下结果：

元素 40 在列表中的索引为：3

我们可以看到，Collections.binarySearch()方法成功地找到了元素 40 在已排序列表中的索引。

需要注意的是，如果要在一个自定义对象的集合中查找元素，binarySearch()方法默认使用元素自身的自然顺序（按照实现了java.lang.Comparable接口的比较器进行比较）。如果自定义对象不实现Comparable接口，则需要在binarySearch()方法中传入一个比较器。

示例：在自定义对象集合中查找元素

假设我们有一个Person类，其中包含了姓名、年龄和性别这三个属性。我们希望在一个已排序的Person对象集合中查找某个特定姓名的人，并返回该人所在的索引。

首先，我们需要在Person类中实现Comparable接口，以便Collections.binarySearch()方法能够使用对象自身的自然顺序来进行比较。

public class Person implements Comparable<Person> {
    private String name;
    private int age;
    private String gender;

    // 构造方法和getter/setter省略

    // 实现Comparable接口中的compareTo方法
    @Override
    public int compareTo(Person other) {
        return this.name.compareTo(other.getName());
    }
}

上述代码中，我们在Person类中实现了Comparable<Person>接口，并重写了compareTo()方法，使其按照name属性的字典序进行比较。

接下来，我们可以使用Collections.binarySearch()方法在已排序的Person集合中查找某个特定姓名的人，并返回其所在的索引。

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

public class BinarySearchExample2 {
    public static void main(String[] args) {
        // 创建一个已排序的Person对象列表
        List<Person> persons = new ArrayList<>();
        persons.add(new Person("Amy", 20, "Female"));
        persons.add(new Person("Bob", 30, "Male"));
        persons.add(new Person("Cathy", 25, "Female"));
        persons.add(new Person("David", 35, "Male"));
        persons.add(new Person("Emma", 28, "Female"));

        // 创建一个比较器，用于按姓名比较Person对象
        Comparator<Person> nameComparator = new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                return p1.getName().compareTo(p2.getName());
            }
        };

        // 查找姓名为"David"的人所在的索引
        Person key = new Person("David", 0, "");
        int index = Collections.binarySearch(persons, key, nameComparator);

        // 输出结果
        if (index >= 0) {
            System.out.println("姓名为 David 的人在列表中的索引为：" + index);
        }
        else {
            System.out.println("姓名为 David 的人不存在于列表中。");
        }
    }
}

上述代码中，我们创建了一个比较器nameComparator，用于按照Person对象的姓名进行比较。然后，我们创建了一个名为key的Person对象，它的姓名为"David"，并传入binarySearch()方法进行查找。

注意到我们在binarySearch()方法中传入了比较器nameComparator，以保证能够按照姓名进行比较。

运行上述代码，可以得到以下输出结果：

姓名为 David 的人在列表中的索引为：3

可以看到，Collections.binarySearch()方法成功地找到了姓名为"David"的人所在的索引。

结论

Collections.binarySearch()方法可以高效地在已排序集合中查找元素的索引，其时间复杂度为O(log n)，比线性搜索更加高效。如果要在自定义对象的集合中查找元素，需要使用对象自身的自然顺序（实现Comparable接口）或传入一个比较器。