Efficient way to get first value larger than x in a list?

Question

I have two sorted arrays, Haystack and Needles. I need to iterate over Needles, and each time find the first point in Haystack with a value larger than that Needle, in order to perform the next step.

For example:

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    

So the index I should get is the first index equal to or lower than the needle value.

The obvious approach is just to iterate from the beginning of the haystack for each needle, or to iterate onward from the last found index (as Needles is also sorted).

But part of my brain is shouting "bisection!". Would a bisection actually be faster here, since the compiler will find it harder to optimise than a simple block read and iteration? Would it need an incredibly long Haystack to be worthwhile?

Answer 1

You need to consider the scenario,

n*lg(m) < n+m,

Where n is the size of Needle and m is the size of Haystack.

Therefore, it all depends on the various combination of values of n and m.