查找“包含”间隔之间的值的所有索引的最快方法是什么？

Question

假设我有两个长度相同的数组（

N

），

x

和

y

。他们满足以下条件：

1. x[i]

   严格小于

   y[i]

   。
2. 没有关于间隔长度y[i]-x[i]的

   先验

   信息。虽然，它通常比

   max(x)-min(x)

   或

   max(y)-min(y)

   小得多。
3. 可以对

   x[i]

   或

   y[i]

   进行排序。然而，为了具有任何意义，应保留原始的

   x[i]

   和

   y[i]

   对。因此，

   x[i]

   和

   y[i]

   不能同时排序。

现在，我有了一个价值

z

。对于某些指标

i

，满足

x[i]<=z<y[i]

。我如何找到所有此类索引？显然我可以遍历所有

0...N-1

来检查所有情况，但考虑到条件2，这是极其浪费。如果只是为了找到最接近的索引，二分搜索会很好用，但是改变间隔长度是有问题的。

我想到的一种方法是，首先对

x

或

y

进行排序，然后使用二分搜索来获取要迭代的第一个元素。例如，如果我对

x

进行排序，那么我可以准确地知道

x

何时超过

z

。然后，我必须从

0

迭代到最大索引。我可以迭代大约一半的元素，而不是迭代整个

N

元素——这仍然没有用。

有什么建议来解决这个问题吗？特别是，我想做的是分别找到一个数字

z

和另一个数字数组的索引，我不确定这是否会改变问题。

Answer 1

进行快速选择而不是排序。这应该会给出

z

在

x

中的排名，以及发现

O(log(n))

较小值的

x[i]

范围。

在每个中快速选择将获得整个 ansaer，类似于

O(log(n)^2)

。