Sorted Arrays

Binary search finds an item in a sorted array by inspecting the middle of a shrinking range, and each comparison eliminates about half of the remaining possible positions.

Programming

Finding an Item Without Reading Every Line

Imagine a sorted list of one million numbers and a single target value you need to locate. A routine that checks each item in turn might have to look at every one of them. Binary search takes a different approach. It works on a sorted array, inspects one item near the middle of the range that could still hold the target, and uses the result of that single comparison to throw away a large block of positions at once.

The routine you will trace in this article takes a sorted array and a target value. It returns the position where the target sits, or the value -1 when the target is absent. As you read, keep one question in mind: how does the routine decide where to look next, and how does it know when to stop?

What do you think happens?

The array below is sorted. You search for the value 20, which is not in it. Before reading on, what do you think a correct search should return, and what would tell the routine that it can stop?

Reveal answer

Answer:

It should return -1. The routine stops when the range of possible positions becomes empty, which means the target cannot be in the array.

A search routine has to answer two questions: where the target is, and whether it is there at all. A routine that only handles successful searches can look correct on many inputs, so the failing case deserves equal attention.

Why Sorting Makes Discarding Safe

The key fact behind binary search is that inspecting a single item can rule out a large block of positions, but only because the array is sorted. If the items increase from left to right, comparing the target with one item tells you which side of that item the target must lie on. If the middle value is larger than the target, then the target cannot be at the middle or anywhere to its right, because every item on that side is larger still. All of those positions can be discarded in one move.

If the middle index holds 16 and the target is 23, every position to the left of index 4 is also smaller than 23 and the target cannot lie there. In a sorted layout, comparing with one middle item reveals which side is safe to discard.

Tracing a Successful Search

The source describes the routine in a particular way. Rather than repeatedly modifying the array, it keeps track of the range of locations that could still contain the target. Two boundary variables mark that range: a lower boundary and an upper boundary. At each step the routine looks at the item in the middle of the range, and the result of that single comparison leads to one of three outcomes: the middle item is the target, the target must be in the lower part of the range, or the target must be in the upper part.

The working example uses the sorted array 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, which occupies indices 0 through 9. The target is 23. The lower boundary starts at index 0 and the upper boundary starts at index 9. The middle of the range is the index halfway between them, rounded down.

Worked example

Searching for 23 in a sorted array of ten items

Find the position of 23 in the sorted array 2, 5, 8, 12, 16, 23, 38, 56, 72, 91.

1
Pass 1: range 0 to 9
The middle index is 4, which holds 16. Since 23 is greater than 16, the target cannot be at index 4 or anywhere to its left. The lower boundary moves to 5.
2
Pass 2: range 5 to 9
The middle index is 7, which holds 56. Since 23 is less than 56, the target cannot be at index 7 or to its right. The upper boundary moves to 6.
3
Pass 3: range 5 to 6
The middle index is 5, which holds 23. The middle item is the target, so the search stops and reports position 5.

Result

The target 23 is at index 5. Three comparisons were needed, and the range shrank from ten possible positions to one.

Each pass inspects the middle of the current range, compares, and discards one half. The lower and upper boundaries move inward until the middle item is the target.

Tracing a Search That Fails

The source states the stopping rule plainly. The loop runs while the lower boundary has not passed the upper boundary. It ends in one of two ways: by finding the target at the middle, or by the range becoming empty. When the upper boundary falls below the lower boundary, the target is known not to be in the array, and the routine returns -1.

Worked example

Searching for 20, which is absent

Use the same sorted array 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 and search for 20.

1
Pass 1: range 0 to 9
The middle index is 4, which holds 16. Since 20 is greater than 16, the lower boundary moves to 5.
2
Pass 2: range 5 to 9
The middle index is 7, which holds 56. Since 20 is less than 56, the upper boundary moves to 6.
3
Pass 3: range 5 to 6
The middle index is 5, which holds 23. Since 20 is less than 23, the upper boundary moves to 4.
4
Check: lower 5, upper 4
The upper boundary is now below the lower boundary. The range has no positions left, so the target cannot be in the array.

Result

The routine returns -1. The search concluded that 20 is absent after three comparisons, without ever needing to read the whole array.

A Python Version of the Routine

The code below follows the description above: two boundary variables, a loop that runs while the range is non-empty, a single comparison per pass, and a return of -1 when the range becomes empty. It is an illustration written for this article, not a copy of the source's implementation.

Code walkthrough

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))
print(binary_search(numbers, 20))

1
Line 2 and 3 set the boundaries to the first and last valid indices.
2
Line 4 keeps the loop running while low has not passed high.
3
Line 5 finds the middle index of the current range.
4
Lines 6 and 7 stop the search when the middle item equals the target.
5
Lines 8 and 10 discard the half of the range that cannot contain the target.
6
Line 11 returns -1 when the loop ends with an empty range.

low and high are the two boundary variables that mark the range of possible positions
The while condition keeps the loop running only while the range is not empty
The middle index is computed from both boundaries at every pass
Returning mid ends the search when the middle item is the target
Moving low or high past the middle is the discard step that removes half the range
Returning -1 after the loop reports that the target is absent

Output

5
-1

Comparing Steps as Arrays Grow

The source makes the efficiency argument concrete. Each step leaves about half of the remaining locations, so the number of locations left falls quickly. From a range of 1000 locations, the search narrows to about 500, then about 250, then about 125, and so on, until only one location remains after about 10 steps. Looking through every element in turn would take far longer on the same array.

Rule

Because the number of steps is approximately the base-2 logarithm of the number of items, a million items need only about 20 steps. The logarithm grows very slowly. A tenfold or even a thousandfold increase in items adds only a few more steps. Linear search, which may inspect every element, grows in step with the size of the array itself. In the worst case it needs one comparison per item, so a million items can require up to a million comparisons.

For 1,000 items, binary search needs about 10 comparisons where linear search may need up to 1,000. For 1,000,000 items, binary search needs about 20 where linear search may need up to 1,000,000. The gap widens as the array grows.

Mistakes When Tracing the Search Range

Common mistake
Applying binary search to an unsorted array
What it looks like
Searching the list 91, 2, 56, 8 for 8 and discarding the right half after comparing with the middle value.
Why it fails
The discard decisions are only valid when the array increases from left to right. An unsorted middle value says nothing reliable about the positions beside it.
Do this instead
Confirm the array is sorted before using binary search, or use linear search when it is not.
Common mistake
Forgetting the empty-range case
What it looks like
A routine that loops only while low is less than high and returns nothing afterward.
Why it fails
A search for an absent value must end somewhere. Without the empty-range check, the routine has no defined answer for failing searches, which is the case that is easiest to overlook.
Do this instead
Loop while low is not past high, and return -1 after the loop ends.
Common mistake
Discarding the middle item along with the wrong half
What it looks like
After comparing 23 with the middle value 16, setting low to the middle index instead of one past it.
Why it fails
The middle item has already been checked and is not the target, so keeping it in the range wastes a comparison and can cause the range to stop shrinking.
Do this instead
Move low to middle plus one, or high to middle minus one, so the checked item leaves the range.
Common mistake
Treating the number of steps as proportional to the array size instead of its logarithm

Practice: Trace a Search by Hand

MEDIUM

Use the sorted array 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, which occupies indices 0 through 9. Trace binary search for the value 72. For each pass, write the lower boundary, the upper boundary, the middle index, the value at the middle, and your decision. Report the final result.

Hints

Start with low at 0 and high at 9, then compute the middle index as the midpoint rounded down.
Compare the target with the middle value. If the target is larger, move low past the middle. If it is smaller, move high before the middle.
The first middle index is 4, which holds 16. Decide which side of index 4 can contain 72.

Your attempt (not saved)

HARD

Without tracing every pass, explain in two or three sentences why binary search on this array cannot need more than about four comparisons to answer for any target, and why the answer is still correct when the target is absent.