如何在有序Row列表中高效查找b值刚好大于x的元素？

算力阿峰

2026-8-14

解决方案：利用二分查找实现高效查找

当然有更高效的方案——二分查找，完全不需要遍历整个列表。

核心原因

题目中明确说明"按a排序时b也自动排序"，这意味着整个列表的b值本身是单调有序序列（结合需求来看应为递增），而二分查找的核心前提就是数据有序，刚好匹配这个场景。

具体实现思路

直接基于b值进行二分查找，目标是找到第一个b值大于x的Row记录，步骤如下：

初始化左指针left = 0，右指针right = rows.size() - 1
初始化结果变量result = null
循环执行直到left > right：
1. 计算中间索引mid = left + (right - left) / 2（避免整数溢出）
2. 如果rows[mid].b > x：
  - 把当前rows[mid]设为候选结果（它符合b>x，但可能左边还有更早的符合条件的记录）
  - 调整右指针right = mid - 1，继续向左查找
3. 否则（rows[mid].b <= x）：
  - 调整左指针left = mid + 1，向右寻找更大的b值
循环结束后，result就是第一个b值刚好大于x的Row记录

伪代码示例

Row findFirstBGreaterThanX(int x, List<Row> rows) {
    int left = 0;
    int right = rows.size() - 1;
    Row result = null;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        Row current = rows.get(mid);
        
        if (current.b > x) {
            result = current;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}