Alex Rivera | Logout

Is binary search optimal in worst case?

Asked 2011-09-28T05:26:51.657
11

Is binary search optimal in worst case? My instructor has said so, but I could not find a book that backs it up. We start with an ordered array, and in worst case(worst case for that algorithm), any algorithm will always take more pairwise comparisons than binary search.

Many people said that the question was unclear. Sorry! So the input is any general sorted array. I am looking for a proof which says that any search algorithm will take at least log2(N) comparisons in worst case(worst case for the algo in consideration).

algorithm math binary-search
Edit
Report

1 Answer

0

It depends on the nature of the data. For example the English language and a dictionary. You could write an algorithm to achieve better than a binary search by making use of the fact that certain letters occur within the English language with different frequencies.

But in general a binary search is a safe bet.

answered 2011-09-28T05:33:46.210

Your Answer