0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

Binary search is done by reaching the middle of the sorted array in O(1) time which is done through indexing .The case which you are telling is not exactly how binary search work.

Its because computer can reach the middle element in no time and you have to linearly go to the center point in case of your car plate example.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ +1 In other words, binary search takes $O(\log n)$ time only if we assume something as efficient as a Random Access Machine (RAM) model of computation. There is no implementation of binary search on a (single-tape, one-sided) Turing machine that runs in logarithmic time, for instance. What Craig describes is almost like implementing binary search on a doubly linked list, which also fails. If Craig could jump from car to car, the number of jumps would indeed be logarithmic. $\endgroup$ – Patrick87 Aug 15 '14 at 16:02
  • $\begingroup$ But how did computer scientists come to the idea that the RAM model of computation is realistic? In the real physical world (even the world of electronics), space is always a consideration. You can't reach the middle car in no time. $\endgroup$ – Craig Feinstein Aug 15 '14 at 16:49
  • 1
    $\begingroup$ Organisation of Memory is such that you can reach any location if you know its address.Its not like going through all memory location in order to access a memory location. $\endgroup$ – monkey Aug 15 '14 at 16:58
  • 1
    $\begingroup$ @CraigFeinstein The RAM model is just a model and, like other models, it's an imperfect description of how the world works. However, modern memory architectures are generally modeled fairly well by RAM because the way the hardware is arranged and accessed, differences in distances are unimportant compared to the number of such accesses. Earlier memory technologies, like sequentially-accessed tape drives, are better-suited to other kinds of search mechanisms (like sequential search). In summary, why the RAM model? Because it's a better fit for how real computers work than a linear-access model. $\endgroup$ – Patrick87 Aug 15 '14 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.