Uniform Binary Search explanation and lookup table [duplicate]

• You are asking for "time complexity". That's the wrong notion here (problems have complexity, algorithms have costs such as runtime) but I understand it as "What is the Big-Oh?". And that won't change. Uniform binary search is a "bit jostling" optimisation that improves runtime in certain situations, but only in the constants. (You can't search faster than in $O(\log n)$ in an array, at least without preprocessing in $\Omega(n \log n)$. Do you know why?) Therefore, any analysis at the Landau level of granularity applies to both variants. – Raphael Apr 1 '14 at 8:07