1. 问题背景与挑战
假设我们有一个自定义的Row类，包含两个整型字段a和b：
class Row {
int a;
int b;
}我们持有一个Row对象的列表。数据的一个特性是，如果列表按a字段排序，那么它也自动按b字段排序。我们的目标是编写一个函数find(int x, List
对于包含1000条记录甚至更多的大型列表，简单地通过迭代遍历整个列表来查找目标元素（时间复杂度为O(N)）效率低下。我们需要一种更优化的数据结构或查找方法来避免全量迭代。
2. 解决方案：利用二分查找
在已排序的列表中查找元素，二分查找（Binary Search）是效率最高的算法之一，其时间复杂度为O(log N)。Java的java.util.Collections类提供了binarySearch()方法，可以方便地对List进行二分查找。关键在于，binarySearch()方法可以接受一个Comparator，允许我们根据自定义的比较逻辑进行查找。
立即学习“Java免费学习笔记（深入）”；
2.1 定义Row类
首先，我们需要一个功能完备的Row类，包括构造函数、getter方法以及用于调试的toString()方法：
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
static class Row {
int a, b;
public int getA() { return a; }
public int getB() { return b; }
Row(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public String toString() {
return "Row(" + a + ", " + b + ")";
}
}2.2 定义自定义比较器
由于我们需要根据b字段进行查找，因此需要一个比较器来指导binarySearch()方法。Comparator.comparing()方法提供了一种简洁的方式来创建基于某个字段的比较器：
static final ComparatorORDER_BY_B = Comparator.comparing(Row::getB);
这个ORDER_BY_B比较器将用于对Row对象列表进行排序，并作为binarySearch()方法的参数。
2.3 实现查找函数
核心的查找逻辑封装在find方法中。这个方法需要处理Collections.binarySearch()返回的不同情况，尤其是当目标元素未找到时。
static Row find(int x, Listrows) { int size = rows.size(); // 使用Collections.binarySearch查找x对应的Row对象 // 注意：这里的new Row(0, x)仅用于提供一个Row对象作为搜索键， // 其a字段的值不重要，因为我们通过ORDER_BY_B比较器只比较b字段。 int i = Collections.binarySearch(rows, new Row(0, x), ORDER_BY_B); int index; if (i >= 0) { // 情况1：精确匹配，x的值在列表中找到 index = i; } else { // 情况2：未找到精确匹配 // Collections.binarySearch在未找到时返回 (-(insertion point) - 1) // 其中 "insertion point" 是元素应该被插入以保持列表有序的索引。 // 例如，如果返回-1，则插入点为0；如果返回-2，则插入点为1，以此类推。 // 插入点可以通过 -i - 1 计算得到。 int insertionPoint = -i - 1; if (insertionPoint >= size) { // 情况2.1：x大于列表中所有元素的b值。 // 此时，插入点会等于列表的大小（size）。 // 根据题目要求，返回列表中最后一个元素。 index = size - 1; } else { // 情况2.2：x未找到，但介于列表中的某些元素之间，或小于所有元素。 // insertionPoint就是第一个大于x的元素的索引。 // 这符合“b comes right after x”或“b >= x”的逻辑。 index = insertionPoint; } } return rows.get(index); }
index计算逻辑详解：
- i >= 0: 表示x对应的Row对象在列表中被精确找到，i就是其索引。直接返回rows.get(i)。
- i : 表示x对应的Row对象未在列表中找到。Collections.binarySearch()在这种情况下返回一个负值，其计算方式为 (-(insertion point) - 1)。
-
insertion point: 这是如果将x插入到列表中以保持其排序顺序，x应该被插入的索引。
- 如果x小于列表中所有元素，insertion point为0。
- 如果x大于列表中所有元素，insertion point为rows.size()。
- 否则，insertion point是第一个大于x的元素的索引。
- 因此，通过insertionPoint = -i - 1，我们可以得到这个插入点。
- insertionPoint >= size: 这意味着x比列表中所有元素的b值都大。在这种情况下，根据题目要求，我们返回列表的最后一个元素，即rows.get(size - 1)。
- insertionPoint : 这意味着x虽然未精确匹配，但其值介于列表中的元素之间，或者小于所有元素。此时，insertionPoint就是第一个b值大于或等于x的元素的索引。这正是我们所寻找的“b comes right after x”的元素。
-
insertion point: 这是如果将x插入到列表中以保持其排序顺序，x应该被插入的索引。
2.4 示例用法
为了演示上述逻辑，我们创建一个main方法来测试find函数：
public static void main(String[] args) {
// 原始数据列表
List rows = Arrays.asList(
new Row(20, 2),
new Row(40, 4),
new Row(50, 5),
new Row(70, 7));
// **重要：对列表进行排序**
// binarySearch要求列表必须是根据所使用的Comparator进行排序的。
// 尽管问题描述中提到“sorted by a, the data automatically gets sorted by b”，
// 但为了确保binarySearch的正确性，我们应该显式地使用ORDER_BY_B进行排序。
List orderByB = rows.stream().sorted(ORDER_BY_B).collect(Collectors.toList());
System.out.println("Sorted list: " + orderByB);
// 测试不同x值
for (int i = 0; i < 9; ++i) {
System.out.println("find " + i + " : " + find(i, orderByB));
}
}
运行结果：
Sorted list: [Row(20, 2), Row(40, 4), Row(50, 5), Row(70, 7)] find 0 : Row(20, 2) find 1 : Row(20, 2) find 2 : Row(20, 2) find 3 : Row(40, 4) find 4 : Row(40, 4) find 5 : Row(50, 5) find 6 : Row(70, 7) find 7 : Row(70, 7) find 8 : Row(70, 7)
从输出可以看出，当x小于或等于某个元素的b值时，返回该元素；当x大于所有元素的b值时（如x=8），返回列表中最后一个元素Row(70, 7)。
3. 注意事项与总结
- 列表排序是前提：Collections.binarySearch()方法要求被搜索的列表必须是根据传入的Comparator进行升序排序的。如果列表未排序或排序方式与比较器不一致，binarySearch()的结果将是不可预测的。在实际应用中，确保数据在执行查找操作前已经排序是至关重要的一步。
- 性能优势：相较于O(N)的线性查找，二分查找提供了O(log N)的时间复杂度。对于包含1000条记录的列表，线性查找可能需要最多1000次比较，而二分查找最多只需要约10次比较（log2(1000) ≈ 9.96），显著提升了查找效率。
- 通用性：这种方法不仅适用于int类型的字段，也可以扩展到其他可比较的数据类型（如String, double等），只需相应地调整Comparator的实现。
- 边界条件处理：find方法中的index计算逻辑巧妙地处理了所有边界条件，包括精确匹配、目标值小于所有元素、目标值大于所有元素以及目标值介于现有元素之间的情况，确保了结果的正确性。
通过以上方法，我们可以有效地在大型自定义对象列表中执行高效的近似查找，避免了全量迭代带来的性能开销。
