What Big-O equation describes my search?

Question

I have a sorted array of doubles (latitudes actually) that relatively uniformally spread out over a range of -10 to -43. Now, if I did a binary search over that list I get O(log N).

But, I can further optimise by search by having a lookup table where I have 34 keys (-10 to -43) that can then jump straight to the starting point of that number.

Eg: -23.123424 first look up key 23 and know the start-end range of all -23 values. I can then binary search from the middle of that.

What would my Big-O look like?

Answer 1

It's still O(log n). Consider: it takes constant time to look up the starting indices in your integer lookup table, so that part doesn't add anything. Then it's O(log n) to do the binary search. Actually it will take roughly log n/34 because you expect to search through an array 34 times smaller on average (the values are distributed in 34 different intervals with boundaries from -43 to -10), but constant multipliers aren't considered in big-O notation.

Answer 2

It would still be O(log N), but for a reduced dataset (think smaller value for N).

Since the lookup table provides ca. 1/34, which is close to 1/32 or 5 steps in the binary search, you might want to benchmark, if this really helps things: The additional code paths with lots of cache misses and one or the other wrong branch prediction/pipeline clearing might make this slower than the direct binary search.

Additionally, if lookup time for an in-memory table is the bottleneck, you might want to consider representing your lats as Int32 values - definitly precise enough, but much faster to search through.