Binary search

Prerequisites

• Sorted arrays and zero-based indexing.
• Linear search, the baseline to beat.
• Logarithms: $\log_2 n$ is how many times you can halve $n$ before reaching 1.

The analogy

How it works

Data requirement: the array must be sorted.

Start with one search by hand

Look for 9 in [1, 3, 5, 7, 9, 11, 13]. The range starts as indices 0 to 6. Guess first, then open "Check".

Finish the picture

Now search the same array for 4, which isn't there.

• Steps 1 and 2. 7 > 4, so go left to 0..2; the middle is 3. Predict where you go next.
  Check

  3 < 4, so go right: the range is index 2 only.

• Step 3. a[2] = 5. Predict: what happens to the range?
  Check

  5 > 4, so hi becomes 1 while lo is 2. The range is empty, so return −1. Still only 3 comparisons.

The rule in plain words

Keep a range lo..hi where the target could be. Look at the middle. If it's the target, done. If it's too small, move lo past it; if too big, move hi before it.

When the range is empty, the target isn't there.

The code

Read this code after you have done one search by hand. It will make more sense.

int binary_search(const int a[], int n, int x) {
    int lo = 0, hi = n - 1;                 /* x can only be in a[lo..hi] */
    while (lo <= hi) {                      /* range not empty */
        int mid = lo + (hi - lo) / 2;       /* avoids overflow of lo + hi */
        if (a[mid] == x) return mid;
        if (a[mid] < x) lo = mid + 1;       /* x is to the right */
        else hi = mid - 1;                  /* x is to the left */
    }
    return -1;
}

flowchart TD
  A["lo = 0, hi = n - 1"] --> B{"lo <= hi ?"}
  B -->|no| F["Return -1: not found"]
  B -->|yes| C["mid = middle of lo..hi"]
  C --> D{"compare a[mid] with x"}
  D -->|equal| E["Return mid"]
  D -->|"a[mid] < x"| G["lo = mid + 1"]
  D -->|"a[mid] > x"| H["hi = mid - 1"]
  G --> B
  H --> B
          

How fast is it?

Each comparison halves the range, so after $k$ comparisons about $n / 2^k$ elements are left. The search ends when that reaches 1:

For our 7 elements: $\lfloor \log_2 7 \rfloor + 1 = 3$, exactly what we used.

Common mistakes

• Running it on unsorted data. It doesn't crash; it silently gives wrong answers.
• Computing (lo + hi) / 2, which can overflow for huge indices; use lo + (hi - lo) / 2.
• Updating with lo = mid or hi = mid, which never excludes mid and can loop forever.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• It needs sorted data because only order lets one comparison rule out a whole half.
• It is $O(\log n)$ because each comparison halves the range, and you can halve $n$ only $\log_2 n$ times.
• It stops with "not found" when lo > hi because an empty range leaves no place for the target.
• mid ± 1 is essential because mid has already been checked and must leave the range.
• Extra space is $O(1)$ because the loop version only keeps lo, hi and mid.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is binary search like the "guess my number" game?
   Sample answer

   Guessing the middle means every "higher" or "lower" answer rules out half the numbers. Binary search uses the middle element of a sorted array the same way.

2. Walk through a search for 9 in [1, 3, 5, 7, 9, 11, 13].
   Sample answer

   Middle 7 is too small, so go right; middle 11 is too big, so go left; middle 9 matches at index 4. Three comparisons.

3. Why does the code compute mid as lo + (hi - lo) / 2?

   A good answer mentions what can go wrong with lo + hi.

   Sample answer

   For very large arrays, lo + hi can exceed the largest int and overflow to a negative number. hi - lo never overflows.

4. So what is binary search, in one sentence?
   Sample answer

   It searches a sorted array by checking the middle of the current range and keeping only the half that can still contain the target.

5. Why does binary search only work on sorted data?

   A good answer explains what one comparison tells you.

   Sample answer

   If the middle is smaller than the target, sorting guarantees everything to its left is smaller too, so that half can go. Without order, one comparison says nothing about the other elements.

6. What are its best, average and worst cases?
   Sample answer

   Best $O(1)$ if the first middle is the target. Average and worst $O(\log n)$, at most $\lfloor \log_2 n \rfloor + 1$ comparisons. Extra space $O(1)$.

7. How does binary search report that a value is missing?
   Sample answer

   The range shrinks until lo passes hi. The range is then empty, and the function returns −1.

8. When would you still use linear search instead?
   Sample answer

   When the data is unsorted and you only search once, since sorting costs more than one linear scan. Also for tiny arrays, where linear search is fast enough and simpler.

9. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the overflow detail and the exact $\lfloor \log_2 n \rfloor + 1$ bound. I'd keep the guessing-game analogy, one search on the 7-element array, and "sorted data, halve each time, $O(\log n)$".

External resources

• Khan Academy: Binary search: an interactive lesson with the guessing game.
• GeeksforGeeks: Binary search: iterative and recursive code in several languages.
• Wikipedia: Binary search: variants, history and the overflow bug.
• MIT OCW 6.006 Introduction to Algorithms: lectures on searching sorted arrays.

Videos

• YouTube search: binary search explained: pick a short walkthrough.