Binary search visualization

Binary search finds a value in a sorted array by comparing the target with the middle element and discarding half of the remaining range in every round. It needs about log₂ n rounds instead of the n comparisons that a scan needs.

How it works

1. Keep a range lo to hi that can still contain the target. At first it covers the whole array.
2. Look at the middle index, mid.
3. If array[mid] equals the target, return mid.
4. If array[mid] is smaller than the target, the target can only be to the right: set lo = mid + 1.
5. Otherwise it can only be to the left: set hi = mid - 1.
6. Repeat while lo <= hi. When the range is empty, return -1.

A worked example of binary search

Search for 21 in the sorted array [3, 8, 12, 17, 21, 26, 34]:

1. lo = 0, hi = 6, mid = 3, value 17. 17 is less than 21, so set lo = 4.
2. lo = 4, hi = 6, mid = 5, value 26. 26 is greater than 21, so set hi = 4.
3. lo = 4, hi = 4, mid = 4, value 21. 21 equals 21: return 4.

The result is 4, found in 3 rounds and 5 comparisons (this lesson counts "is it equal?" and "is it less?" as separate comparisons). A linear scan would also need 5 comparisons for this target, so there is no gain on 7 elements. The gap opens as the array grows.

Now search for 10, which is missing:

1. lo = 0, hi = 6, mid = 3, value 17. 17 is greater than 10, so set hi = 2.
2. lo = 0, hi = 2, mid = 1, value 8. 8 is less than 10, so set lo = 2.
3. lo = 2, hi = 2, mid = 2, value 12. 12 is greater than 10, so set hi = 1.

After round 3 the range is empty, so the result is -1.

Binary search pseudocode

Indexes start at 0, as in the code of this lesson, and A is sorted in ascending order.

BINARY-SEARCH(A, n, target)
1  lo = 0
2  hi = n - 1
3  while lo <= hi
4      mid = floor((lo + hi) / 2)
5      if A[mid] == target
6          return mid
7      if A[mid] < target
8          lo = mid + 1
9      else hi = mid - 1
10 return -1

Each round removes the middle element and one side of it. In a language with fixed-width integers, write line 4 as mid = lo + floor((hi - lo) / 2), because lo + hi can overflow: a bug of exactly this kind was reported in Java's library implementation in 2006. JavaScript numbers do not overflow at these sizes, so the lesson uses the simpler form.

Time and space complexity

Every comparison halves the range. An array of 1,000 elements needs at most 10 rounds, and an array of 1,000,000 needs at most 20. Doubling the array adds only one more round.

Complexity

Best case time	O(1)
Average case time	O(log n)
Worst case time	O(log n)
Extra space	O(1)

• Best, O(1): the target is exactly the first middle element.
• Average, O(log n): the range is halved on each round until it holds one element or none.
• Worst, O(log n): the target is missing or found on the last round, after about log₂ n halvings.
• Space, O(1): the iterative version only keeps lo, hi and mid.

When to use it, and when not to

• Use it when the data is already sorted, or will be searched many times, so the cost of sorting (O(n log n)) is paid once.
• It needs random access to any index. A linked list does not qualify, because reaching the middle costs O(n).
• On unsorted data it is wrong, not just slow: the argument "bigger than the middle means it is to the right" only holds when the array is sorted, so it can return -1 for a value that is really there. Use linear search instead.

Where binary search is used

• Standard libraries. Java's Arrays.binarySearch, C++'s std::binary_search and std::lower_bound, and Python's bisect module all halve a sorted range. bisect is also the usual way to find where a new value belongs in a list that must stay sorted.
• Database indexes. A B-tree index keeps its keys in sorted order inside each page, so once the tree has led to the right page, the database finds the key in it by halving the sorted keys. This is why an indexed lookup in a table of millions of rows touches only a handful of pages.
• Finding a bug with git bisect. The commits are in order, and the question "does the bug appear here?" changes from no to yes only once. git bisect tests the middle commit and discards half of the range, so about 10 tests are enough for 1,000 commits.

Common mistake and edge cases

Related algorithms and variations

The lower-bound and upper-bound versions return the first or the last position of a value, which fixes the duplicates caveat above. Interpolation search guesses the position from the values themselves: on evenly spread keys it needs about log log n comparisons, but its worst case is O(n) (Knuth treats it in section 6.2.1). A binary search tree keeps the same left-or-right decisions in a structure that also accepts inserts.

The opposite trade is linear search, which needs no sorting, and linear search vs binary search compares the two on the same inputs. To get a sorted array in the first place, see merge sort.