Java 中 Arrays 二分查找自定义键的深入解析

简介

在 Java 中，Arrays 类提供了二分查找方法 binarySearch，它能在已排序的数组中高效地查找元素。不过，标准的 binarySearch 方法只能依据元素的自然顺序或指定的比较器进行查找。当我们需要根据元素的某个特定属性（即自定义键）来查找时，就需要进行一些额外的处理。本文将详细介绍 Arrays binary search java custom key 的基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地利用这一技术。

基础概念

二分查找

二分查找是一种高效的查找算法，其时间复杂度为 $O(log n)$。它的工作原理是将已排序的数组分成两部分，然后根据目标值与中间元素的大小关系，决定继续在左半部分还是右半部分查找，直到找到目标值或确定目标值不存在。

自定义键

自定义键是指我们不使用元素本身的自然顺序，而是根据元素的某个特定属性来进行查找。例如，一个 Person 对象数组，我们可能想根据 Person 对象的 age 属性来进行查找，而不是根据 Person 对象的默认比较规则。

使用方法

1. 准备已排序的数组

二分查找要求数组必须是已排序的。如果数组未排序，二分查找的结果将是不确定的。

2. 实现自定义比较器

为了根据自定义键进行查找，我们需要实现一个自定义的比较器。比较器是一个实现了 Comparator 接口的类，它定义了两个元素之间的比较规则。

3. 使用 `Arrays.binarySearch` 方法

Arrays 类提供了多个重载的 binarySearch 方法，其中一个可以接受一个自定义的比较器。

以下是一个简单的代码示例：

import java.util.Arrays;
import java.util.Comparator;

class Person {
    String name;
    int age;

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

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Person{name='" + name + "', age=" + age + "}";
    }
}

public class CustomKeyBinarySearch {
    public static void main(String[] args) {
        Person[] people = {
                new Person("Alice", 20),
                new Person("Bob", 25),
                new Person("Charlie", 30)
        };

        // 按年龄排序
        Arrays.sort(people, Comparator.comparingInt(Person::getAge));

        // 自定义比较器，根据年龄进行比较
        Comparator<Person> ageComparator = Comparator.comparingInt(Person::getAge);

        // 要查找的年龄
        int targetAge = 25;
        Person targetPerson = new Person("", targetAge);

        // 使用二分查找
        int index = Arrays.binarySearch(people, targetPerson, ageComparator);

        if (index >= 0) {
            System.out.println("找到年龄为 " + targetAge + " 的人: " + people[index]);
        } else {
            System.out.println("未找到年龄为 " + targetAge + " 的人");
        }
    }
}

在这个示例中，我们创建了一个 Person 类，并根据 age 属性对 Person 对象数组进行排序。然后，我们使用自定义的比较器 ageComparator 来进行二分查找。

常见实践

查找具有特定属性的对象

如上述示例所示，我们可以根据对象的某个属性（如年龄、ID 等）来查找对象。

处理重复元素

如果数组中存在重复的自定义键，二分查找可能会返回任意一个匹配元素的索引。如果需要找到所有匹配的元素，可以在找到一个匹配元素后，向左右两侧扩展查找。

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

class Book {
    String title;
    int price;

    public Book(String title, int price) {
        this.title = title;
        this.price = price;
    }

    public int getPrice() {
        return price;
    }

    @Override
    public String toString() {
        return "Book{title='" + title + "', price=" + price + "}";
    }
}

public class FindAllMatches {
    public static void main(String[] args) {
        Book[] books = {
                new Book("Book1", 20),
                new Book("Book2", 30),
                new Book("Book3", 30),
                new Book("Book4", 40)
        };

        // 按价格排序
        Arrays.sort(books, Comparator.comparingInt(Book::getPrice));

        // 自定义比较器，根据价格进行比较
        Comparator<Book> priceComparator = Comparator.comparingInt(Book::getPrice);

        // 要查找的价格
        int targetPrice = 30;
        Book targetBook = new Book("", targetPrice);

        // 使用二分查找
        int index = Arrays.binarySearch(books, targetBook, priceComparator);

        List<Book> matchingBooks = new ArrayList<>();
        if (index >= 0) {
            // 向左扩展查找
            int left = index;
            while (left >= 0 && priceComparator.compare(books[left], targetBook) == 0) {
                matchingBooks.add(books[left]);
                left--;
            }

            // 向右扩展查找
            int right = index + 1;
            while (right < books.length && priceComparator.compare(books[right], targetBook) == 0) {
                matchingBooks.add(books[right]);
                right++;
            }
        }

        if (!matchingBooks.isEmpty()) {
            System.out.println("找到价格为 " + targetPrice + " 的书:");
            for (Book book : matchingBooks) {
                System.out.println(book);
            }
        } else {
            System.out.println("未找到价格为 " + targetPrice + " 的书");
        }
    }
}

最佳实践

确保数组已排序

在使用二分查找之前，一定要确保数组是已排序的。可以使用 Arrays.sort 方法进行排序。

选择合适的比较器

比较器的实现要准确反映自定义键的比较规则。如果比较器实现错误，二分查找的结果将是错误的。

处理查找失败的情况

Arrays.binarySearch 方法在查找失败时会返回一个负数。可以通过对返回值取反减一来得到插入点的位置。

int index = Arrays.binarySearch(people, targetPerson, ageComparator);
if (index < 0) {
    int insertIndex = -(index + 1);
    System.out.println("未找到，插入点位置: " + insertIndex);
}

小结

通过本文的介绍，我们了解了在 Java 中使用 Arrays 类的二分查找方法进行自定义键查找的基础概念、使用方法、常见实践和最佳实践。自定义键查找可以帮助我们根据元素的特定属性进行高效查找，提高程序的性能。在使用时，要注意确保数组已排序，选择合适的比较器，并正确处理查找失败的情况。

参考资料

《Effective Java》
《数据结构与算法分析（Java 语言描述）》