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

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查找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);
}

public static void main(String[] args) {
    // 原始数据列表
    List<Row> 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<Row> 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)