Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why does binary search take $O(\log n)$ time?

, , No Comments
Problem Detail: 

My question seems like an elementary question, but it's really not.

Suppose I have one million cars in a line sorted in alphabetical order by license plate. I am standing at the top of the line with the car with license plate AAA111. I want to find the car with license plate ZZZ999. I could do binary search to find the car with license plate ZZZ999, but I'm still going to have to walk the distance of one million cars, not a distance on the order of $\log 10^6$.

So this is why I'm asking how or why did computer scientists come up with the idea that binary search takes $O(\log n)$ time?

Asked By : Craig Feinstein

Answered By : imhobo

This is only possible in data structures which allow random access like arrays and vectors.

So if you already know that you have to access the last car , then you can do it in O(1) time. Data structures like linked lists won't allow you to perform a binary search in O(logn)

The example you have mentioned is similar to using binary search on a linked list. So it will need O(n) time as you will need to traverse all the nodes to reach the last node in the worst case.

So your argument that you cannot reach the middle car in no time is valid in your example but not in data structures which offer such properties.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29155

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback