How Binary Search Works

Binary search finds a value in a sorted list by repeatedly halving the search space. Compare the target to the middle element: if smaller, search the left half; if larger, the right. This gives

time instead of

for linear search — finding an item in a million entries takes about 20 steps.