Optimality of Binary Search
Posted
by
templatetypedef
on Stack Overflow
See other posts from Stack Overflow
or by templatetypedef
Published on 2010-12-31T17:42:54Z
Indexed on
2010/12/31
17:53 UTC
Read the original article
Hit count: 192
Hello all-
This may be a silly question, but does anyone know of a proof that binary search is asymptotically optimal? That is, if we are given a sorted list of elements where the only permitted operation on those objects is a comparison, how do you prove that the search can't be done in o(lg n)? (That's little-o of lg n, by the way.) Note that I'm restricting this to elements where the only operation permitted operation is a comparison, since there are well-known algorithms that can beat O(lg n) on expectation if you're allowed to do more complex operations on the data (see, for example, interpolation search).
Thanks so much! This has really been bugging me since it seems like it should be simple but has managed to resist all my best efforts. :-)
© Stack Overflow or respective owner