Computer Science › Section F · Algorithms › Topic F.5

Recursive structures: binary search

A loop repeats a task by going round again; recursion repeats it by handing a smaller copy of the task to itself. Binary search, which finds an entry in a sorted list of a million items in at most 20 looks, is the classic example.

Repetition as a subtask

Imagine looking up a word in a dictionary and finding that its definition uses another word you do not know. You pause, look up the second word, then return to the first definition and finish reading it. The second lookup is the same task as the first, carried out inside it. That is recursion: a function that, as part of its own work, calls itself on a smaller version of the problem. A loop, as in "Iterative structures: sequential search and insertion sort", finishes one pass and then starts the next; recursion starts the next stage inside the current one and returns to finish it afterwards.

The idea of binary search

Searching a sorted list does not require checking every entry. Look at the middle entry first. If it is the target, you are done. If the target is smaller, it can only be in the front half; if larger, only in the back half. Either way, half the list is ruled out with one look, and the remaining half is searched in exactly the same way. Guessing a number from 1 to 100 with "higher" or "lower" replies works like this. If the part left to search becomes empty, the target is not in the list. The method only works because the list is sorted.

Binary search in pseudocode

We search positions Low to High of a sorted list L, and div divides and rounds down, so Mid is the lower middle when the range has an even number of entries.

\begin{array}{l} \texttt{def BinarySearch(L,} \\ \qquad \texttt{Target, Low, High):} \\ \quad \texttt{if (Low > High):} \\ \qquad \texttt{return 0} \\ \quad \texttt{Mid = (Low + High) div 2} \\ \quad \texttt{if (L[Mid] == Target):} \\ \qquad \texttt{return Mid} \\ \quad \texttt{if (Target < L[Mid]):} \\ \qquad \texttt{return BinarySearch(L,} \\ \qquad\qquad \texttt{Target, Low, Mid - 1)} \\ \quad \texttt{return BinarySearch(L,} \\ \qquad\quad \texttt{Target, Mid + 1, High)} \end{array}

The first call is BinarySearch(L, Target, 1, length(L)). It returns the target's position, or 0 if the target is absent.

Worked example: a successful search

Search L = [4, 9, 13, 18, 22, 27, 31, 36, 40, 45, 51, 58, 63, 70, 77] for 45. 1. Low = 1, High = 15, so Mid = 8 and L[8] = 36. 45 is larger, so call BinarySearch on positions 9 to 15. 2. Mid = (9 + 15) div 2 = 12 and L[12] = 58. 45 is smaller, so call on positions 9 to 11. 3. Mid = 10 and L[10] = 45, a match, so this call returns 10. 4. Each earlier call returns whatever its own call returned, so 10 passes back up and the first call returns 10. Three entries were examined; sequential search would have checked ten.

Worked example: a failed search

Search the same list for 20. 1. Positions 1 to 15: L[8] = 36, and 20 is smaller, so call on 1 to 7. 2. L[4] = 18, and 20 is larger, so call on 5 to 7. 3. L[6] = 27, and 20 is smaller, so call on 5 to 5. 4. L[5] = 22, and 20 is smaller, so call on positions 5 to 4. 5. Now Low = 5 > High = 4: the range is empty, so this fifth call returns 0. 6. The fourth, third, second and first calls each pass the 0 back. The answer, not found, took four looks at the list. At the moment of step 5, five copies of the function existed, four of them waiting.

Activations and base cases

Each call creates an activation: a fresh copy of the function with its own Low, High and Mid. Only the newest activation is running; the others are suspended, each waiting for the call it made to return. Like a loop, recursion needs control. A base case, also called the degenerative case, is a situation answered without calling again: here, an empty range or a match. The first call sets things up, which is the initialisation. Every other case calls itself on a strictly smaller range, which is the modification. Because the range shrinks by at least one each time, an empty range or a match must be reached, so the search always ends.

A simpler recursion and a broken one

Powers show the pattern in miniature. Define Power(B, E): if E == 0, return 1; otherwise return B * Power(B, E - 1). Power(2, 3) calls Power(2, 2), which calls Power(2, 1), which calls Power(2, 0). That fourth activation hits the base case and returns 1, and the waiting activations multiply on the way back: 2, then 4, then 8. Remove the base case and the calls never stop: E becomes -1, -2 and so on. A real computer keeps every waiting activation in memory, so it soon runs out of room and the program crashes with an error called a stack overflow.

How fast is binary search?

Each look at the list halves the part still to be searched, so the number of looks grows very slowly. With the lower-middle rule, binary search on n entries examines at most \(\lfloor \log_2 n \rfloor + 1\) of them, where \(\lfloor x \rfloor\) means x rounded down. For 15 entries that is 4, for 1,000 entries 10, and for 1,000,000 entries 20. Sequential search may need all n. The topic "Efficiency and correctness" turns this comparison into a general way of measuring algorithms. The catch is the precondition: the list must already be sorted, and sorting takes time of its own.

Recursion, loops and recursive sorts

Loops and recursion are equally powerful: anything one can compute, the other can too. Binary search can be rewritten with a while loop that updates Low and High, which avoids storing many activations. Recursion shines when a problem splits into smaller copies of itself. Merge sort splits a list in half, sorts each half recursively and merges the two sorted halves; even in its worst case it needs only about \(n \log_2 n\) comparisons, and it is stable, but needs extra memory. Quicksort partitions the list around a pivot entry and sorts each part recursively; it averages on the order of \(n \log_2 n\) and works in place, but bad pivots push it towards \(n^2\), and the standard version is not stable.

Common mistakes to avoid

First, using binary search on an unsorted list: it can miss a target that is present. Second, a missing or unreachable base case, which recurses until memory runs out. Third, recursive calls that do not shrink the problem, such as calling on Low to Mid instead of Low to Mid - 1, which can repeat the same range for ever. Fourth, forgetting to return the result of the recursive call, so the answer found deep down never reaches the first call. Fifth, mixing up the middle rule: rounding up instead of down changes which entries are examined, though both rules work.

Key takeaways

Recursion repeats a task by calling the same function on a smaller version of it, inside the current call. Binary search examines the middle of a sorted range and recurses on the half that could hold the target. Each call is an activation; base cases (an empty range, or a match) stop the calls, and a range that shrinks every time guarantees the search ends. Binary search examines at most ⌊log₂ n⌋ + 1 entries: 20 for a million. Loops and recursion are equally powerful. Merge sort and quicksort are recursive sorts averaging on the order of n log₂ n comparisons.

Flashcards

Flashcard

Recursion

A function calling itself on a smaller version of its problem

The repeat happens inside the current call.

Test your understanding

Question 1 of 5

BinarySearch, as in the pseudocode with Mid rounded down, searches 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 for 23. Which entries does it examine, in order?

Question 2 of 5

What is the greatest number of entries binary search examines in a sorted list of 1,000 entries?

Question 3 of 5

Which situations are the base cases of the BinarySearch function?

Question 4 of 5

Power(B, E) returns 1 if E == 0 and otherwise B * Power(B, E - 1). How many activations of Power exist in total while computing Power(3, 4)?

Question 5 of 5

Which statement about the recursive sorts is true?

← Previous topicNext topic →