c++ - 在列表中获取大于 x 的第一个值的有效方法？

Question

我有两个排序数组，Haystack 和 Needles。为了执行下一步。

例如:

double [] dHaystack = { 1.2, 2.6, 7.0, 9.3, 19.4 }
double [] dNeedles  = { 1.4, 6.4, 6.5, 7.0, 10.3 }

//  expected indices     0    1    1    2    3    

所以我应该得到的索引是第一个等于或小于针值的索引。

明显的方法是从大海捞针的开头为每根针迭代，或者从最后找到的索引开始迭代(因为 Needles 也是排序的)。

但是我大脑的一部分在喊“平分!”。这里二分法实际上会更快吗，因为编译器会发现它比简单的 block 读取和迭代更难优化？是否需要一个非常长的 Haystack 才有值(value)？

Answer 1

你需要考虑场景，

n*lg(m) < n+m,

其中 n 是 Needle 的大小，m 是 Haystack 的大小。

因此，这完全取决于 n 和 m 值的各种组合。