java - 搜索矩形的排序列表

Question

我有一个矩形列表，以通常的方式创建:

List<Rectangle> rects = new ArrayList<>();

添加了一些矩形(全部具有非零宽度和高度)。列表包含的矩形数量可以是 0 到 10,000 之间的任意值，通常在 4,000 到 6,000 之间。

该列表按矩形原点的 X 坐标升序排序，然后按重复的 X 坐标的 Y 坐标升序排序(尽管两个或多个具有相同 X 坐标的矩形很少见)。

我已经验证排序是否正确完成(我正在使用带有自定义比较器的 Collections.sort)。

我需要一个方法，它接受两个整数 x 和 y 作为输入，并返回找到的第一个包含点 (x,y) 的矩形，如果列表中没有矩形包含该点，则返回 null。

public Rectangle findContainingRectangle(int x, int y)

天真的方法确实提供了所需的功能，即循环遍历列表并调用每个 Rectangle 上的 contains 方法，但这太慢了。

在程序运行时，List 会被修改，但与需要搜索 List 的速率相比，修改速率可以忽略不计，因此需要相对较慢的初始化的算法就可以了。

我查看了 Collections.binarySearch 但不知道如何使用它。我对 Java 没有太多经验，所以如果有另一个 Collection 可以与 List 类似地使用，但更适合我需要的搜索类型，那么那就太好了(我已经阅读了有关 Maps 和 Sets 等内容的文档，但没有不认识任何优点)。

Answer 1

在维护排序列表的同时，您可以在“X”坐标上使用二分搜索来查找包含所需“X”的矩形候选，然后在“Y”坐标上使用二分搜索。

您应该自己实现二分搜索，我看不到使用 Collections.binarySearch 方法的方法。

预期复杂度:O(log n)，n 是矩形的数量。 (这有点多，因为您可能有重复项)

但是，为此，您应该在添加其他实例时保持数组排序(在每次插入后排序)。