For the array search part, don't forget that vector instructions exist these days. With SSE2, for example, you can do four 32-bit float comparisons in parallel, _mm_movemask to put the result in an integer register, then bsr/bsf on that. ARM Neon has all this too.

Show Post

If you have a lot of floats and you need to binary search, you can use this variant: unsigned logl = ceil_log_2(y.size()); int i = 0; for (unsigned k = 1 << (logl-1); k > 4; k >>= 1) { int t = i + k; if (yt >= y[t]) i = t; // Conditional move instruction }

Show Post

After this, i is now pointing at an aligned subsequence of four floats that you can do the vector comparison trick on. This is the fastest way I've found to do this kind of search on modern hardware, assuming that you can't exploit the distribution of y somehow (e.g. bucketing).

Show Post

Unfortunately I guess there is none. Perhaps a binary search can help, but I can't think of a O(1) algorithm

Show Post

I think this is a very sound approach. The rule of thumb I got from my friend who builds fuzzers is that for lists up to ~1000 elements, the fastest thing you can do is a linear search so a good initial guess plus that sounds optimal.

Show Post