When does an O(log n) algorithm beat an O(n) one, and how would you demonstrate that with code?
When the data is sorted, or when you can sort it once and then look things up many times.
A linear search walks through the list from the start and stops when it finds what it is looking for. A binary search looks at the middle of the list, throws away the half that cannot hold the answer, and does it again. Each round halves what is left, so after twenty rounds there is nothing left, and twenty rounds is enough for a million items.
def linear_search(items, target):
for i, value in enumerate(items):
if value == target:
return i
return -1
def binary_search(items, target):
low = 0
high = len(items) - 1
while low <= high:
middle = (low + high) // 2
if items[middle] == target:
return middle
if items[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
So what changes? The number of comparisons. The linear search does up to a million of them and the binary search does about twenty. And that difference is not a small improvement. It is the difference between a program that finishes and one that does not.
There are two prices to pay for the binary search. The first one is that the list has to be sorted, and sorting costs O of n log n, so if you are only going to look things up once then the linear search is often the better answer. The second one is that the list has to support random access, so a linked list would be no better than a linear search.
So the rule to remember is this. A binary search pays off when the data is sorted, when you look things up more than once, and when the list is an array rather than a linked list.
The last question in this topic works out the actual numbers.