0
$\begingroup$

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?

$\endgroup$

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