How efficient is binary search?
In each iteration, we are cutting the list in half. The time complexity is O(log N)
.
A sorted list of 64
elements will take at most log
2
(64) = 6
comparisons.
In the worst case:
Comparison 1: We look at the middle of all
64
elementsComparison 2: If the middle is not equal to our search value, we would look at
32
elementsComparison 3: If the new middle is not equal to our search value, we would look at
16
elementsComparison 4: If the new middle is not equal to our search value, we would look at
8
elementsComparison 5: If the new middle is not equal to our search value, we would look at
4
elementsComparison 6: If the new middle is not equal to our search value, we would look at
2
elements
When there’s 2
elements, the search value is either one or the other, and thus, there is at most 6
comparisons in a sorted list of size 64
.
Instructions
A sorted data-set speeds up searching by a significant amount!
Without any knowledge about the ordering, we would resort to a linear search taking O(N)
time.