Logarithmic complexity

Binary search is O(log n), where n is the number of elements in the array. This logarithm (base 2) answers a simple question: how many times can n be divided by 2 before reaching 1? This is exactly the number of steps needed in the worst case.

Look at how the number of steps grows very slowly compared to the array size:

n (size)          maximum steps (log2(n) rounded up)
8                 3    (8 -> 4 -> 2 -> 1)
16                4    (16 -> 8 -> 4 -> 2 -> 1)
1 000             10
1 000 000         20
1 000 000 000     30

Multiplying the array size by 1000 (from 1,000 to 1,000,000) only adds about 10 steps, whereas a linear search (element by element) would see its number of comparisons multiplied by 1000 in the worst case. That is why binary search is so valuable on large amounts of data: searching among a billion elements takes only about thirty comparisons.

We can visualise the shrinking of the interval as a tree: each step divides the size of the remaining zone by two, until reaching a zone of a single element.

size 16
   |
   v (divide by 2)
size 8
   |
   v
size 4
   |
   v
size 2
   |
   v
size 1   (end: we have found it or the target is absent)

Keep in mind: this logarithmic complexity assumes the array is already sorted. If the array is not sorted, it must first be sorted (cost O(n log n) with a good sort), unless you only do a single search, where a direct linear search in O(n) is sometimes simpler and faster overall.