Binary search

Overview

Recall questions on the binary search algorithm and its sorted-data precondition, tracing successful and unsuccessful searches, best and worst-case and space complexity, maximum comparisons, sorting before searching, and moving pointers past the middle.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe the binary search algorithm.

   Model answer

   Set a low pointer to the first position and a high pointer to the last. Find the middle position between them and compare the item there with the target. If it matches, the search succeeds. If the target is smaller, the high pointer moves to just below the middle; if it is larger, the low pointer moves to just above the middle. Repeat on the remaining half. If the low pointer passes the high pointer, the target is not present.

2. 2

   What must be true of the data before a binary search can be used, and why?

   Model answer

   It must be sorted. The algorithm's whole logic is that comparing with the middle item tells you which half the target must be in, and that conclusion only follows if the data is in order. Run on unsorted data it may discard the half that actually holds the target and wrongly report it as absent; it can stumble on the value by luck, but the result cannot be relied on.

3. 3

   Trace a binary search for 19 in the list 3, 7, 11, 15, 19, 23, 29.

   Model answer

   The pointers span all seven items; the middle item is 15. Since 19 is larger, the search continues in 19, 23, 29, whose middle item is 23. Since 19 is smaller, the search continues in 19 alone, whose middle item is 19 itself, so the search succeeds. Three comparisons in total.

4. 4

   Trace a binary search for 20 in the list 3, 7, 11, 15, 19, 23, 29, and say how the algorithm knows to stop.

   Model answer

   The middle item is 15, and 20 is larger, so continue in 19, 23, 29. The middle item is 23, and 20 is smaller, so continue in 19 alone. The middle item is 19, and 20 is larger, so the low pointer moves past the high pointer. The section left to search is now empty, which is how the algorithm knows 20 is absent, and it reports failure after three comparisons.

5. 5

   What is the best case for a binary search?

   Model answer

   O(1), when the target happens to be the middle item of the whole list and is found on the very first comparison.

6. 6

   Why is a binary search O(log n) in the worst case?

   Model answer

   Because each comparison discards half of the items still under consideration. Starting from n, the number remaining goes n, n over 2, n over 4 and so on down to 1, and the number of halvings needed is log to base 2 of n. Only that many comparisons can ever be made.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.