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();
int i = Collections.binarySearch(rows, new Row(0, x), ORDER_BY_B);
int index = i >= 0 ? i : i <= -size - 1 ? size - 1 : -i - 1;
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));
List<Row> orderByB = rows.stream().sorted(ORDER_BY_B).collect(Collectors.toList());
for (int i = 0; i < 9; ++i)
System.out.println("find " + i + " : " + find(i, orderByB));
}
2条答案
按热度按时间vbkedwbf1#
最简单的方法是从一个排序的列表开始。一旦列表被排序,你可以使用二进制搜索将可能的值减少到2,而不是像你通常在搜索时所做的那样寻找一个完全匹配。
您需要做的另一件事是建立两个基本案例,这将帮助您避免索引越界问题:这两种情况是,
一旦基本情况都试过了,就可以简单地使用折半搜索将你的选择减少到两个值,然后你所需要做的就是比较实际值和存储在列表中两个选择的索引中的数字之间的差的绝对值。
我提出了下面的lambda函数来查找最接近的整数(尽管,它可能比上面的- O(n)?-慢)
样品运行:
第一个
qmelpv7a2#
您可以像这样使用
Collections.binarySearch()
。输出: