This question already has an answer here:

Please can anyone explain me the worst ,average and best case running time for the Unifrom binary search .. Also how can the lookup table be explained?


marked as duplicate by Raphael Apr 1 '14 at 7:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ We have dozens of similar questions and this is a standard result (i.e. found in literature). What have you tried, and where specifically did you get stuck? $\endgroup$ – Raphael Apr 1 '14 at 7:40
  • $\begingroup$ This is not Binary Search ... This is a UNIFROM BINARY SEARCH @Raphael $\endgroup$ – user2845482 Apr 1 '14 at 8:01
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 1 '14 at 8:07
  • $\begingroup$ @Raphael why cant we search faster than O(logn) and please can you explain how is the lookup table used in the Uniform binary search for optimization? $\endgroup$ – user2845482 Apr 1 '14 at 8:38
  • $\begingroup$ These are two distinct questions; it'd be best if you posted each as a new question post here. Take care to do some research, think on the material, then elaborate on what you understand and formulate a question as pointed as possible. For instance, "Explain concept X?" is almost always a bad query. $\endgroup$ – Raphael Apr 1 '14 at 9:15