Data structures and algorithms 0/7

DSA, Arrays and searching

What is binary search?

Also called bisection, half-interval search

395 words · 2 min read

Say you have a sorted array of a million numbers and want to know whether 7,412 is one of them. Checking the numbers one by one from the left can take a million comparisons. Binary search finds a value in a sorted array by comparing it with the middle element, which rules out half of the array, and repeating the same step on the half that is left. For a million numbers it never has to look at more than 20 of them.

The binary search loop

In code, the search keeps two variables, left and right: the first and the last position where the target could still be. At the start they are the two ends of the array, positions 0 and n−1n - 1. As long as the range from left to right holds at least one position, the loop probes the middle one, mid, and compares its value with the target:

  • If the value at mid equals the target, the search is over: the target is at mid.
  • If the value is less than the target, mid and every position before it are ruled out, so left moves to mid + 1.
  • If the value is greater than the target, mid and every position after it are ruled out, so right moves to mid - 1.

Every pass either ends the search or takes mid out of the range, so the range gets shorter each time and the loop has to end. The loop only removes positions whose values are too small or too large to be the target, so if left passes right and the range is empty, the target is not in the array.

How many probes can a search take? A probe leaves at most half of the positions that were in the range, because neither side of mid holds more than half of them. A million positions become at most 500,000 after one probe, 250,000 after two, and fewer than two after 19. So at most one position is left for the 20th probe, and a million values never take more than 20 probes:

1,000,000219=1,000,000524,288≈1.9 positions left after 19 probes\frac{1{,}000{,}000}{2^{19}} = \frac{1{,}000{,}000}{524{,}288} \approx 1.9 \text{ positions left after 19 probes}

Halve the candidate range with binary search

In this stepper you make the decision at each probe. The purple cell is mid, the line under the cells gives its answer, and you choose which side of mid to keep searching. A wrong choice is explained and not applied.

Find the first position whose value is at least 12. Position n stands for past the end, and counts as YES.

  1. 03lo
  2. 18
  3. 211
  4. 314
  5. 420
  6. 527
  7. nnhi

Mid is position 3. 14 is at least 12: YES.

probes: 0, candidates still open: 7, saved answer: -

  • mid
  • probed YES
  • probed NO
  • ruled out
Binary search Find the first YES of a question that flips once, whether the candidates are positions in a sorted array or possible answers such as times and speeds. Read the full lesson