java 的 arraylist 本身不提供二分查找方法,但可以通过调用 collections.binarysearch() 静态方法来提升查找效率。使用前必须确保列表已按自然顺序或指定比较器排序,否则结果不可预测。该方法将线性搜索的 o(n) 复杂度降低为对数级的 o(log n),适合在数据量大且频繁查询的场景下使用。

Collections.binarySearch() 如何返回索引与未找到时的处理逻辑
当列表有序时,Collections.binarySearch() 会返回目标元素的索引;若元素不存在,则返回负值,具体为 (insertion point) - 1。插入点是指第一个大于该元素的索引位置。开发者需通过判断返回值是否小于零来区分“找到”与“未找到”,并可通过取反减一还原插入点,用于后续插入操作以维持有序性。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BinarySearchExample {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);
// 查找存在的元素
int indexFound = Collections.binarySearch(list, 30);
System.out.println("Found 30 at index: " + indexFound); // Output: 2
// 查找不存在的元素
int indexNotFound = Collections.binarySearch(list, 25);
System.out.println("Not found 25, insertion point is: " + (indexNotFound - 1)); // Output: 1
}
}
自定义对象列表进行二分查找需要满足什么条件
对于非基本类型的对象列表,Collections.binarySearch() 要求列表中的元素实现 Comparable 接口,或者在调用时传入一个 Comparator。如果既没有实现接口也没有提供比较器,程序会在运行时抛出 ClassCastException。此外,比较逻辑必须与列表的排序依据完全一致,否则会导致查找失败或返回错误的索引。
使用 Husky 将 pre-commit、pre-push 和 commit-msg 检查集成到仓库中,以便代理和开发人员在更改离开工作站之前运行相同的本地防护措施。
立即学习“Java免费学习笔记(深入)”;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
class Person implements Comparable<Person> {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
return Integer.compare(this.age, other.age);
}
@Override
public String toString() {
return name + "(" + age + ")";
}
}
public class CustomObjectSearch {
public static void main(String[] args) {
List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Charlie", 35));
// 必须先排序
Collections.sort(people);
// 使用默认比较器查找
int idx = Collections.binarySearch(people, new Person("Bob", 25));
System.out.println("Index of Bob: " + idx); // Output: 1
// 使用自定义比较器按名字查找
Comparator<Person> byName = Comparator.comparing(p -> p.name);
// 注意:列表是按年龄排序的,用名字比较器查找会失败或结果不确定
// 正确做法是创建按名字排序的新列表或使用兼容的比较器
}
}
二分查找在未排序的 ArrayList 上运行会发生什么
如果在未排序的 ArrayList 上直接调用 Collections.binarySearch(),方法不会报错,但返回的结果是不可靠的。它可能返回正确的索引(巧合),也可能返回错误的索引,甚至返回表示未找到的负值。这是因为二分查找算法依赖于数据的单调性假设,无序数据破坏了这一前提。因此,在使用前务必先调用 Collections.sort() 进行排序。

















