Java Collections.binarySearch 方法
上次修改时间：2025 年 4 月 20 日
Collections.binarySearch 方法是一个用于高效搜索已排序列表的实用程序。它实现了二分查找算法，该算法提供 O(log n) 的时间复杂度。为了获得正确的结果，列表必须按升序排序。
Collections.binarySearch 概述
Collections.binarySearch 方法是一个用于高效搜索已排序列表的实用程序。它实现了二分查找算法，该算法提供 O(log n) 的时间复杂度。为了获得正确的结果，列表必须按升序排序。
二分查找通过反复将搜索区间减半来工作。它将目标值与数组的中间元素进行比较。根据比较结果，它继续搜索列表的左半部分或右半部分。
binarySearch 方法有两个主要变体。一个适用于元素的自然排序，而另一个允许自定义比较器。两者都返回搜索键在列表中找到时的索引。
如果列表中找到了键，该方法将返回其索引，该索引表示键在已排序列表中的位置。
如果未找到键，该方法将返回一个负值。该值计算为 -(insertionPoint) - 1，其中 insertionPoint 是在保持列表排序顺序的情况下将插入键的索引。
返回的负值有两个目的：它表明列表中不存在键，并提供了关于可以在哪里添加它的位置的信息。
此外，如果列表元素基于指定的比较器或自然排序无法相互比较，该方法将抛出 ClassCastException。
基本 binarySearch 示例
此示例演示了 binarySearch 的最简单用法。我们创建一个已排序的整数列表并搜索一个值。二分查找必须对列表进行排序才能正常工作。
package com.zetcode;
import java.util.Collections;
import java.util.List;
public class BasicBinarySearch {
public static void main(String[] args) {
List<Integer> numbers = List.of(1, 3, 5, 7, 9, 11, 13);
// Search for existing value
int index1 = Collections.binarySearch(numbers, 7);
System.out.println("Index of 7: " + index1);
// Search for non-existing value
int index2 = Collections.binarySearch(numbers, 8);
System.out.println("Index of 8: " + index2);
// Calculate insertion point for 8
if (index2 < 0) {
int insertionPoint = -index2 - 1;
System.out.println("8 should be inserted at: " + insertionPoint);
}
}
}
此代码显示了基本的二分查找用法。我们搜索存在的值 7，以及不存在的值 8。对于不存在的值，我们计算插入点。
输出显示了找到的值的索引以及缺失值的计算插入点。这演示了二分查找在存在和不存在元素时的行为。
使用字符串的 binarySearch
此示例展示了 binarySearch 在字符串列表中的使用。字符串按字典顺序进行比较。列表必须按升序排序。
package com.zetcode;
import java.util.Collections;
import java.util.List;
public class StringBinarySearch {
public static void main(String[] args) {
List<String> words = List.of("apple", "banana", "cherry",
"date", "elderberry", "fig");
// Search for existing string
int index1 = Collections.binarySearch(words, "cherry");
System.out.println("Index of 'cherry': " + index1);
// Search for non-existing string
int index2 = Collections.binarySearch(words, "grape");
System.out.println("Index of 'grape': " + index2);
// Case-sensitive search
int index3 = Collections.binarySearch(words, "Cherry");
System.out.println("Index of 'Cherry': " + index3);
}
}
此示例演示了使用二分查找的字符串搜索。请注意，字符串比较区分大小写。未找到 'Cherry'（以大写 C 开头），因为列表中包含小写字符串。
输出显示了成功和不成功的搜索。 'grape' 的负返回值表示它不存在，但将被插入到末尾。
使用自定义对象的 binarySearch
此示例演示了 binarySearch 与自定义对象的使用。对象必须实现 Comparable，或者我们必须提供一个 Comparator。在这里，我们使用 Comparable 定义的自然排序。
package com.zetcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
record Person(String name, int age) implements Comparable<Person> {
@Override
public int compareTo(Person other) {
return this.name.compareTo(other.name);
}
}
public class CustomObjectBinarySearch {
public static void main(String[] args) {
List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 25));
people.add(new Person("Bob", 30));
people.add(new Person("Charlie", 22));
people.add(new Person("David", 35));
// List must be sorted by the same criteria used in compareTo
Collections.sort(people);
// Search by name (natural ordering)
Person key = new Person("Charlie", 0);
int index = Collections.binarySearch(people, key);
if (index >= 0) {
System.out.println("Found: " + people.get(index));
} else {
System.out.println("Not found. Insertion point: " + (-index - 1));
}
}
}
此代码显示了使用自定义 Person 对象的二分查找。Person 实现了 Comparable，以按名称定义自然排序。在搜索之前，我们必须对列表进行排序。
输出演示了按名称的成功搜索。搜索键中的年龄无关紧要，因为仅使用名称进行比较。
使用 Comparator 的 binarySearch
此示例展示了如何将 binarySearch 与自定义 Comparator 一起使用。当我们希望按与自然排序不同的标准进行搜索时，这很有用。
package com.zetcode;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
record Product(String name, BigDecimal price) {}
public class ComparatorBinarySearch {
public static void main(String[] args) {
List<Product> products = new ArrayList<>();
products.add(new Product("Laptop", new BigDecimal("999.99")));
products.add(new Product("Phone", new BigDecimal("699.99")));
products.add(new Product("Tablet", new BigDecimal("399.99")));
products.add(new Product("Monitor", new BigDecimal("249.99")));
// Sort by price using comparator
Comparator<Product> priceComparator = Comparator.comparing(Product::price);
products.sort(priceComparator);
// Search by price
Product searchKey = new Product("", new BigDecimal("399.99"));
int index = Collections.binarySearch(products, searchKey, priceComparator);
if (index >= 0) {
System.out.println("Found at index " + index + ": " + products.get(index));
} else {
System.out.println("Product with price $399.99 not found");
}
}
}
此示例演示了使用自定义比较器按价格进行搜索。产品按价格排序，允许我们按价格范围进行搜索。搜索键中的产品名称无关紧要。
输出显示了按价格的成功搜索。比较器确保在二分查找操作期间仅比较价格值。
使用重复项的 binarySearch
当列表包含重复项时，binarySearch 不保证将返回哪个重复项的索引。此示例显示了具有重复元素的行为。
package com.zetcode;
import java.util.Collections;
import java.util.List;
public class DuplicateBinarySearch {
public static void main(String[] args) {
List<Integer> numbers = List.of(1, 2, 2, 2, 3, 4, 5);
// Search for duplicate value
int index = Collections.binarySearch(numbers, 2);
System.out.println("Index of 2: " + index);
// The exact index among duplicates is not guaranteed
System.out.println("All indices of 2:");
for (int i = 0; i < numbers.size(); i++) {
if (numbers.get(i) == 2) {
System.out.println(i);
}
}
}
}
此代码演示了二分查找在重复项方面的行为。该方法可以返回该值出现的任何索引。为了找到所有出现，需要额外的处理。
输出显示了找到该值的一个可能索引，然后是它出现的所有索引。这突出了二分查找对重复项的限制。
binarySearch 性能
此示例比较了二分查找与线性搜索的性能。对于大型集合，二分查找的 O(log n) 复杂度使其快得多。
package com.zetcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BinarySearchPerformance {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
numbers.add(i);
}
// Binary search timing
long startTime = System.nanoTime();
int index1 = Collections.binarySearch(numbers, 999999);
long endTime = System.nanoTime();
System.out.println("Binary search time: " + (endTime - startTime) + " ns");
// Linear search timing
startTime = System.nanoTime();
int index2 = -1;
for (int i = 0; i < numbers.size(); i++) {
if (numbers.get(i) == 999999) {
index2 = i;
break;
}
}
endTime = System.nanoTime();
System.out.println("Linear search time: " + (endTime - startTime) + " ns");
}
}
此示例测量了二分查找和线性搜索之间的时间差。对于更大的集合，差异变得更加明显。二分查找对于已排序的数据显然更优越。
来源
Java Collections.binarySearch 文档
在本文中，我们深入探讨了 Java Collections.binarySearch 方法。我们涵盖了基本用法、字符串搜索、自定义对象、比较器、重复项和性能。理解二分查找对于在已排序集合中进行高效的数据检索至关重要。
作者
列出所有Java教程。