在Java集合中高效查找自定义对象中“大于等于”的最近值

class Row {
   int a;
   int b;
}

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 + ")";
    }
}

// 定义一个基于b字段进行比较的比较器
static final Comparator<Row> ORDER_BY_B = Comparator.comparing(Row::getB);

static Row find(int x, List<Row> rows) {
    int size = rows.size();
    // 使用Collections.binarySearch进行查找
    // 传入一个“虚拟”的Row对象作为查找键，其b值为x
    int i = Collections.binarySearch(rows, new Row(0, x), ORDER_BY_B);

    // 解析binarySearch的返回值来确定目标元素的索引
    int index;
    if (i >= 0) {
        // 如果i >= 0，表示找到了精确匹配的元素，直接使用该索引
        index = i;
    } else {
        // 如果i < 0，表示未找到精确匹配的元素。
        // binarySearch返回的是 (-(插入点) - 1)。
        // 插入点是该元素在列表中应插入的位置，即第一个大于它的元素的索引。
        // 所以，-i - 1 就是这个插入点。
        int insertionPoint = -i - 1;

        // 处理边界情况：如果x大于列表中所有b值，插入点将是列表大小
        // 此时我们希望返回最后一个元素
        if (insertionPoint >= size) {
            index = size - 1;
        } else {
            // 否则，插入点就是我们寻找的第一个大于或等于x的元素的索引
            index = insertionPoint;
        }
    }
    // 返回找到的Row对象
    return rows.get(index);
}

public static void main(String[] args) {
    // 原始数据，注意它已经按a排序，并且b也随之排序
    List<Row> rows = Arrays.asList(
        new Row(20, 2),
        new Row(40, 4),
        new Row(50, 5),
        new Row(70, 7));

    // 确保列表是按b排序的，这是binarySearch的前提
    // 虽然原始问题说按a排序b也排序，但为了严谨性，这里显式排序
    List<Row> orderByB = rows.stream().sorted(ORDER_BY_B).collect(Collectors.toList());

    System.out.println("Sorted list by B: " + orderByB);

    // 测试不同x值
    for (int i = 0; i < 9; ++i) {
        System.out.println("find " + i + " : " + find(i, orderByB));
    }
}

Sorted list by B: [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)