Binary Search Algorithm Explained

Binary search is an algorithm for finding a target value in a sorted collection by repeatedly halving the range that could still contain it. Instead of checking every element one by one, it compares the target to the middle element, discards the half of the collection the target can’t be in, and repeats — which is why it finds an element in a list of a million items in roughly twenty comparisons instead of up to a million.

The core requirement is sortedness. Binary search doesn’t work on unsorted data; the whole trick depends on being able to conclude, from a single comparison, that an entire half of the remaining range can be safely eliminated.

How it works

Given a sorted array and a target value:

1. Look at the middle element of the current search range.
2. If it equals the target, you’re done.
3. If the target is smaller, the target — if it exists — must be in the left half, so discard the right half and repeat.
4. If the target is larger, discard the left half and repeat.
5. If the range becomes empty, the target isn’t in the collection.

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

Each iteration cuts the remaining search space in half, which is where the algorithm gets its logarithmic running time: O(log n) comparisons in the worst case, versus O(n) for a linear scan that checks every element in order.

Why it’s fast: the math in plain terms

Halving repeatedly is a fast way to shrink a number. Starting from a million elements, one comparison narrows the range to 500,000, then 250,000, then 125,000 — and after about twenty halvings, the range is down to a single element. That’s the essence of O(log n): doubling the input size adds only one more comparison, not a proportional amount of work. See Big O notation for the general framework this falls under, and the master theorem for how this kind of “solve half the problem, recurse” running time is derived formally for divide-and-conquer algorithms in general.

Binary search vs binary search trees

It’s easy to conflate binary search the algorithm with a binary search tree, a data structure. They’re related but distinct: binary search operates on a sorted array and requires no extra structure beyond the array itself, while a binary search tree maintains the sorted-order property as a tree of linked nodes, which makes insertion and deletion efficient in ways a plain sorted array doesn’t support. If your data is static or rarely changes, a sorted array with binary search is simpler and more cache-friendly; if you need frequent insertions and deletions while keeping fast lookups, a balanced binary search tree is usually the better fit.

Common implementation pitfalls

Binary search has a reputation, even among experienced programmers, for being easy to get subtly wrong:

• Integer overflow in the midpoint. mid = (low + high) / 2 can overflow in languages with fixed-width integers if low + high exceeds the maximum representable value. The safer form is mid = low + (high - low) // 2, which avoids the intermediate sum ever exceeding high.
• Off-by-one errors in the bounds. Whether the search range is inclusive (low <= high) or half-open (low < high) changes how low and high need to be updated on each iteration, and mixing conventions is the most common source of infinite loops or missed elements.
• Forgetting the array must be sorted. Running binary search on unsorted data doesn’t error — it just silently returns wrong or inconsistent results, since the “discard half” logic depends entirely on order.
• Duplicate values. A plain binary search returns some index where the target occurs, not necessarily the first or last. Finding the leftmost or rightmost occurrence of a duplicated value needs a small variation of the standard algorithm that keeps narrowing even after finding a match.

Where binary search shows up beyond arrays

The same halving idea generalizes past “find a value in a sorted array.” It applies to any problem where you can define a monotonic condition — one that’s false, then true, across a range — and want the boundary between them: finding the smallest value that satisfies some property, searching a rotated sorted array, or finding an insertion point in a sorted list. This pattern shows up often enough in coding interviews and real optimization problems that it’s worth recognizing separately from the textbook “find this exact value” version. It’s also a close cousin of the two-pointers technique, which likewise exploits sorted order to avoid checking every pair or every element individually — though two pointers moves inward from both ends rather than repeatedly halving a range.

Binary search vs linear search

	Linear search	Binary search
Requires sorted input	No	Yes
Time complexity	O(n)	O(log n)
Extra setup cost	None	Data must be sorted first, O(n log n) if not already
Best for	Small or unsorted collections, one-off lookups	Large sorted collections, repeated lookups

If a collection needs to be searched only once, sorting it purely to enable binary search can cost more than a single linear scan would have. Binary search pays off when the data is already sorted, or when it will be searched many times after being sorted once.

The takeaway

Binary search finds a target in a sorted collection in O(log n) time by discarding half the remaining search space on every comparison, which is dramatically faster than a linear scan once the collection is large. It requires sorted input, is easy to get subtly wrong around midpoint calculation and boundary conditions, and generalizes beyond exact-value lookups to any problem with a monotonic true/false boundary to find. For data that changes frequently, a binary search tree is usually a better fit than repeatedly re-sorting an array.