Binary search checks the middle element of a sorted array. If the target is smaller, discard the right half. If larger, discard the left half. Repeat.
Each step eliminates half the remaining elements. After k steps, you have n/2^k elements left. When n/2^k = 1, you are done. Solving gives k = log₂(n).
This is O(log n). Searching 1 million items takes about 20 steps.