Binary Search Algorithm

A search compares the item with the root, then discards either the left or right subtree, and repeats on the remaining subtree.

Programming

Interactive lab

Try it: Binary Search

How binary search finds a value in a sorted list by checking the middle and throwing away the half that cannot contain it.

How it works

Start with the whole sorted list as the search interval (lo to hi).
Look at the middle value.
If it is the target, stop. If the target is larger, discard the left half; if smaller, discard the right half.
Repeat until the target is found or the interval is empty (not found).

Default run (7 steps): Search for 17 in [2, 5, 9, 13, 17, 21, 30]. The whole array is the search interval: lo = 0, hi = 6. … 17 = 17 — found at index 4 after 3 comparisons.

Educational simulation

Loading the simulation…

Why One Comparison Can Throw Away Half the Items

Suppose you need to find one value among a long list of values that is already sorted from smallest to largest. You could start at the first item and check each one in turn. That works, but it is slow when the list is long. Binary search takes a different approach: it inspects one item and uses the result of that single comparison to decide which part of the list can be ignored from then on.

This article follows the routine as it runs. Keep one question in mind throughout: how does the routine decide where to look next, and how does it know when to stop? A routine that handles only successful searches can look correct on most inputs, so the article also asks what happens when the target is not there at all.

Tracing a Search Through a Sorted Array

The routine keeps two boundary markers, a lower boundary and an upper boundary, that mark the range of positions that could still hold the target. It does not keep modifying the array. At each step it looks at the item in the middle of the current range, compares that item with the target, and the result leads to one of three outcomes: the middle item equals the target and the search ends with success, the target is smaller so the upper half of the range is discarded, or the target is larger so the lower half is discarded.

Consider this sorted array of ten values, stored at positions 0 through 9: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. The example below is generated for teaching and is not from the source. Search for the target 23. Start with the lower boundary at position 0 and the upper boundary at position 9. The middle position is 4, holding 16. Since 23 is greater than 16, every position from 0 to 4 can be discarded, and the lower boundary moves to position 5.

The range is now positions 5 through 9. The middle is position 7, holding 56. Since 23 is smaller than 56, positions 7 through 9 are discarded and the upper boundary moves to position 6. The range is now positions 5 and 6. The middle is position 5, holding 23. That matches the target, so the search stops and reports position 5. Only three comparisons were needed, and the positions 0 to 4 and 7 to 9 were never examined one by one.

After the three comparisons for the target 23, which positions are still candidates, and at which position does the search end? Positions 0 to 4 and 7 to 9 were discarded, positions 5 and 6 remain, and position 5 holds the target.

Worked example

Searching for a target that is absent

Using the same sorted array of values 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 at positions 0 to 9, search for 40. Show how the routine proves that 40 is not in the array.

1
Start the range
Lower boundary is 0 and upper boundary is 9. The middle position is 4, holding 16. Since 40 is greater than 16, the lower boundary moves to 5.
2
Second comparison
The range is positions 5 to 9. The middle is position 7, holding 56. Since 40 is smaller than 56, the upper boundary moves to 6.
3
Third comparison
The range is positions 5 to 6. The middle is position 5, holding 23. Since 40 is greater than 23, the lower boundary moves to 6.
4
Fourth comparison
The range is positions 6 to 6. The middle is position 6, holding 38. Since 40 is greater than 38, the lower boundary moves to 7.
5
Empty range
The lower boundary is now 7 and the upper boundary is 6. The lower boundary has passed the upper boundary, so the range is empty and 40 is known to be absent.

Result

The search returns -1, which signals that the target is not in the array.

Why the Array Must Be Sorted

The key fact 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. Everything on the far side can be discarded in one move.

Without sorting, the same comparison tells you nothing useful. A smaller value could sit anywhere in an unsorted list, so ignoring one half could throw away the only copy of the target. The discard decision is valid only when the array increases from left to right.

Definition

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.

The routine checks whether the lower boundary has passed the upper boundary. As long as the lower boundary is still at or below the upper boundary, at least one candidate position remains. When the upper boundary falls below the lower boundary, the range is empty and the target is known not to be in the array. The routine then returns -1.

A Python Version of the Array Routine

The following Python function is a generated teaching version of the routine described above. It keeps the two boundary variables low and high, inspects the middle position, and either returns the position, discards the lower half, or discards the upper half. It returns -1 when the range becomes empty.

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 target < items[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

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

1
Lines 2 and 3 set the boundaries to cover the whole array.
2
The while condition keeps the loop going while at least one candidate position remains.
3
The middle position is computed from low and high each time through the loop.
4
If the middle item matches, the position is returned immediately.
5
If the target is smaller, high moves to just below mid, discarding the upper half.
6
If the target is larger, low moves to just above mid, discarding the lower half.
7
When the loop ends without a match, the function returns -1.

low and high are the two boundary markers that bracket the candidate range
The loop runs while low has not passed high, so an empty range ends it
mid is the middle position of the current range
Finding the target at mid ends the search and returns its position
A smaller target discards the upper half; a larger target discards the lower half
Returning -1 is the signal that the target is absent

Output

5
-1

What do you think happens?

In the array above, what does the routine return when you search for 40? Make a prediction before reading the answer.

Reveal answer

Answer:

-1

The range shrinks through positions 5, 6, and 7 until low is greater than high. At that point the array is known not to contain 40, so the routine returns -1.

Searching a Binary Sort Tree

A binary sort tree applies the same discard idea to a tree of nodes. Searching for an item starts by comparing it with the root item. If the two are equal, the search is finished. If the sought item is less than the root item, only the left subtree can contain it, so the right subtree is discarded. If the sought item is greater than the root item, only the right subtree needs to be examined, and the left subtree is discarded. The same procedure is then applied to whichever subtree remains.

The tree below is a generated example. Its root is 50. The left subtree has root 30 with children 20 and 40. The right subtree has root 70 with children 60 and 80. Search for 60. Compare 60 with the root 50: since 60 is greater, the entire left subtree rooted at 30 is discarded without examining 30, 20, or 40. Next compare 60 with 70: since 60 is smaller, the right child 80 side is discarded and only the left subtree of 70 remains. Finally 60 is compared with 60, and the search stops there.

Starting at the root, which nodes are visited for the target 60, and at which node does the search end? The visited nodes are 50, 70, and 60; the whole left subtree under 50 is eliminated at the first comparison.

Now search for 45 in the same tree, which is not present. Compare 45 with 50: it is smaller, so go left to 30. Compare 45 with 30: it is greater, so go right to 40. Compare 45 with 40: it is greater, so the search would go right, but there is no right child. The search falls off the tree at that empty spot, which tells you that 45 is not in the tree. This is the tree version of the empty range in the array routine.

Insertion Follows the Search Path

Insertion is similar to search. The procedure first searches the tree for the position where the new item belongs. When that position is found, a new node is created and attached at that place. The search path for an insertion is the same path a search would follow for that item, and the new node takes the place of the empty spot where the search would have fallen off the tree.

Using the tree from the previous section, insert 45. The search path is 50, then 30, then 40, exactly the path traced above. At 40 the search goes right into an empty spot, so the new node 45 becomes the right child of 40. Nothing else in the tree changes.

An empty tree needs its own case. When there is no root yet, there is no comparison to make and no subtree to fall into, so the new node itself becomes the root. Handling this case separately prevents the routine from trying to compare with a root that does not exist.

The source notes that the insertion routine works more like the non-recursive search than the recursive one. The reason is that insertion has to change the tree, and a recursive routine that receives the root as a parameter cannot change the value of the caller's variable. For that reason the source's insertion routine accesses the static member variable root directly.

When Insertion Order Makes the Tree Lopsided

A binary tree is balanced when, for each node, the left subtree has approximately the same number of nodes as the right subtree. Searching and inserting are efficient only when the tree is close to balanced, and the order in which items are inserted decides a great deal about whether it stays that way. If items arrive in a random order, the tree usually comes out approximately balanced. If the order is not random, the tree can become very unbalanced.

The same five values can produce two very different trees. Inserting 10, 20, 30, 40, 50 in that order makes each new value larger than everything before it, so every node goes to the right. The result is a chain five levels deep, and every node has an empty left subtree. Inserting 30, 10, 40, 20, 50 places the values so that each subtree splits more evenly, producing a tree only three levels deep. Both trees follow the same placement rules; only the insertion order differs.

How does the same set of values produce a long lopsided chain in one insertion order and a shorter bushy tree in another? The before group is the chain built by inserting 10, 20, 30, 40, 50 in order; the after group is the bushier tree built by inserting 30, 10, 40, 20, 50.

Counting Steps: Binary Versus Linear Search

Each step of binary search leaves about half of the remaining locations. Starting 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. The number of steps is approximately the base-2 logarithm of the number of items, so a million items need only about 20 steps. Looking through every element in turn would take far longer for the same array.

Rule

Array size	Linear search, worst case	Binary search, approximate steps
1,000	1,000	about 10
2,000	2,000	about 11
4,000	4,000	about 12
1,000,000	1,000,000	about 20

Doubling the array size adds only about one step to binary search, while linear search doubles its worst case.

The table makes the difference concrete. Because the step count grows with the logarithm of the array size, a tenfold or even a thousandfold increase in items adds only a few more steps. Linear search may inspect every element, so its work grows in step with the size of the array itself. This efficiency is the reason the sorted-array requirement and the balance requirement both matter: they are what allow each comparison to discard a large share of the candidates.

Mistakes Beginners Make

Common mistake
Running binary search on an unsorted array
What it looks like
Searching an unsorted list for a value that sits in the half that was just discarded
Why it fails
The discard decision is valid only when the array increases from left to right, so the target may be thrown away even though it is present.
Do this instead
Sort the array first, or use a method that does not rely on order.
Common mistake
Testing only searches that succeed
Why it fails
A routine that only handles found targets can look correct on most inputs but never shows what happens when the range becomes empty.
Do this instead
Test an absent target and confirm that the routine returns -1 or reports the failure.
Common mistake
Assuming every binary sort tree is fast
What it looks like
Inserting 10, 20, 30, 40, 50 in that order and then searching for 50
Why it fails
The placement rules are sound, but the chain produced by this insertion order makes each comparison remove only one item.
Do this instead
Recognize that search and insert speed depend on the tree staying close to balanced, which depends on insertion order.
Common mistake
Forgetting the empty tree case when inserting
Why it fails
With no root there is no node to compare against, so the routine needs a separate branch that makes the new node the root.
Do this instead
Check for an empty tree first, then follow the search path otherwise.
Common mistake
Letting the loop run forever by not updating low or high
Common mistake
Using the middle item as the answer without checking whether it equals the target

Practice: Predict the Search Path

MEDIUM

Using the sorted array 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 at positions 0 to 9, trace a binary search for the target 72. List each middle position you inspect, the value found there, and the new boundaries, then state the position returned. Then repeat the trace for the target 10 and state at which point the range becomes empty.

Hints

Start with low at 0 and high at 9, and compute the middle as the rounded-down average of low and high.
After each comparison, keep only the half that could still contain the target.
For the target 10, watch for the moment low passes high.

Your attempt (not saved)