Binary Search

In Turkish: İkili Arama

Updated September 30, 20263 min read

In short

Binary search is an algorithm that finds a value in a sorted list by repeatedly halving the search range, taking O(log n) time instead of checking every item.

What is binary search?

Binary search looks for a target value in a sorted collection. It compares the target with the middle item: if they match, the search is done; if the target is smaller, it continues in the left half; if it is larger, it continues in the right half. Each step throws away half of the remaining items.

Because the range halves every time, binary search needs at most about log2(n) steps, which is O(log n) time. For a sorted list of one million items that is at most 20 comparisons, and for one billion items about 30, compared with up to a billion checks for a linear search that looks at items one by one. The loop-based version also needs only O(1) extra memory.

It works like the number guessing game where the other player only says higher or lower: the smartest strategy is always to guess the middle of the remaining range. Binary search is used to look up items in sorted arrays, inside database indexes and search trees, in standard library tools such as Python's bisect module, and in git bisect, which finds the commit that introduced a bug by repeatedly halving the commit history.

Binary search only works on sorted data with fast access by index, such as an array; on a linked list, just reaching the middle item takes O(n). It is also easy to get subtly wrong: off-by-one errors in the loop bounds are common, and in languages with fixed-size integers, computing the middle as (low + high) / 2 can overflow, so low + (high - low) / 2 is the safer form. Don't confuse binary search, an algorithm, with a binary search tree, a data structure that stores values so they can be searched the same way.

At a glance

Each comparison with the middle item throws away half of what is left.

Key takeaways

Binary search requires the data to be sorted.
It runs in O(log n) time, compared with O(n) for a linear search.
Each comparison eliminates half of the remaining items.
It needs fast access by index, so it suits arrays rather than linked lists.
Off-by-one mistakes in the loop bounds are the most common bug.

Example

Iterative binary search in Pythonpython

def binary_search(items, target):
    # items must be sorted in ascending order
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid        # found it
        if items[mid] < target:
            low = mid + 1     # target is in the right half
        else:
            high = mid - 1    # target is in the left half
    return -1                 # target is not in the list

print(binary_search([2, 5, 8, 12, 16, 23, 38], 23))  # 5

Readers ask

Why must the list be sorted for binary search?

Binary search decides which half to discard by comparing the target with the middle item. That decision is only correct if everything to the left is smaller and everything to the right is larger, which is true only for sorted data.

What is the time complexity of binary search?

Binary search runs in O(log n) time in the worst and average case, and O(1) in the best case, when the middle item is the target. The loop-based version uses O(1) extra memory, while a recursive version uses O(log n) for the call stack.

Is it worth sorting data just to run a binary search?

Sorting costs O(n log n), so it only pays off if you search the same data many times. For a single lookup, a linear search in O(n) is faster, and for many exact-key lookups a hash table is often better still.