Binary search explained with code in Python, C++ and JavaScript

Binary search finds a value in a sorted array by comparing the target with the middle element and discarding the half that cannot contain it. Each step halves the range, so it needs at most about log2 n steps: 20 for 1,000,000 elements. It runs in O(log n) time but works only on sorted data, or on any yes-or-no test that flips just once.

How does binary search work?

NIST's Dictionary of Algorithms and Data Structures defines binary search as searching a sorted array by repeatedly dividing the search interval in half. Start with an interval covering the whole array. If the target is less than the middle item, keep the lower half. Otherwise keep the upper half. Stop when the value is found or the interval is empty.

Two index variables, lo and hi, mark the interval. The idea that keeps the code correct is the loop invariant: if the target is in the array, it lies between positions lo and hi. Princeton's lecture slides state it as "a[lo] <= key <= a[hi]" when the key is present. Each pass checks the middle item, moves one end past it, and so keeps the invariant while the interval shrinks. When lo passes hi the interval is empty and the target is absent.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

data = [3, 8, 12, 17, 21, 25, 30, 42, 47]
print(binary_search(data, 25))   # found
print(binary_search(data, 26))   # absent

5
-1

Searching for 25 in that nine-element list takes three steps. The first middle is index 4 (value 21), which is too small, so lo moves to 5. The second middle is index 6 (value 30), which is too large, so hi moves to 5. The third middle is index 5, value 25, and the search returns 5. Searching for 26 follows the same path, finds that 25 is too small and 30 too large, and ends with the interval empty and a result of -1.

What is the time complexity of binary search?

Binary search runs in O(log n) time. Princeton's Algorithms text proves it uses no more than lg N + 1 compares in the worst case for a search of N keys, whether the search succeeds or fails. A linear scan of an unsorted array is O(n) and, as the Competitive Programmer's Handbook points out, is the best possible approach when the order of elements is arbitrary.

The gap grows fast with size. Counting loop steps for a target larger than every element, the worst case, gives these figures.

Doubling the array adds only one step. That is the practical meaning of logarithmic growth, covered further in time complexity and Big O notation for beginners.

How do you write binary search in JavaScript and C++?

The logic is identical in every language. The JavaScript version below returns the same results as the Python one. Its final lines show why JavaScript does not suffer from the overflow problem described in the next section: numbers are 64-bit floats, so even the longest possible array index sum is exact.

function binarySearch(a, target) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const data = [3, 8, 12, 17, 21, 25, 30, 42, 47];
console.log(binarySearch(data, 25));  // 5
console.log(binarySearch(data, 26));  // -1

const maxLength = 2 ** 32 - 1;
console.log(maxLength + maxLength, Number.isSafeInteger(maxLength + maxLength));

5
-1
8589934590 true

In C++ the same loop uses int indices. The program below finds the first element not smaller than a value, matches the library function std::lower_bound, and then shows what goes wrong with the naive midpoint.

#include <algorithm>
#include <iostream>
#include <vector>

int lower_bound_index(const std::vector<int>& a, int x) {
    int lo = 0, hi = static_cast<int>(a.size());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int main() {
    std::vector<int> a = {1, 2, 2, 2, 5, 7, 7, 9};
    std::cout << lower_bound_index(a, 2) << " "
              << (std::lower_bound(a.begin(), a.end(), 2) - a.begin()) << "\n";

    int lo = 2000000000, hi = 2100000000, wrapped;
    bool overflow = __builtin_add_overflow(lo, hi, &wrapped);  // GCC and Clang built-in
    std::cout << "lo + hi overflows: " << overflow << ", wrapped to " << wrapped << "\n";
    std::cout << "safe midpoint: " << lo + (hi - lo) / 2 << "\n";
}

1 1
lo + hi overflows: 1, wrapped to -194967296
safe midpoint: 2050000000

Why does the midpoint formula matter?

The obvious midpoint, (lo + hi) / 2, breaks when lo + hi exceeds the largest value the index type can hold. Joshua Bloch reported in a Google Research blog post of 2 June 2006 that the binary search in Java's java.util.Arrays, written by him, had this bug, as did the version that Jon Bentley proved correct in Programming Pearls. It had gone unnoticed for about nine years. The sum overflows to a negative number and the array access fails. Bloch's fix is low + ((high - low) / 2) or an unsigned shift.

The risk depends on the language, because integer types differ.

Bloch notes the bug appears for arrays of 2^30 elements or more, roughly a billion, which was inconceivable in the 1980s when Programming Pearls was written and was common at Google and other places by 2006. Writing lo + (hi - lo) / 2 costs nothing in any language, so it is the safe habit. Princeton's lecture slides also list the history: the first binary search was published in 1946, the first bug-free one in 1962, and the Java library bug was found in 2006.

How do lower bound and upper bound work?

Plain binary search returns any matching index, which is not enough when duplicates exist. Two variants fix this. The lower bound is the first index whose value is at least the target. The upper bound is the first index whose value is greater than the target. Their difference counts how many times a value occurs.

def lower_bound(a, x):
    """First index i with a[i] >= x (len(a) if none)."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(a, x):
    """First index i with a[i] > x (len(a) if none)."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

The two functions differ only in < versus <=. Running them on a list with repeated values shows the difference.

from bisect import bisect_left, bisect_right

a = [1, 2, 2, 2, 5, 7, 7, 9]
print(lower_bound(a, 2), upper_bound(a, 2))       # first and one-past-last 2
print(upper_bound(a, 2) - lower_bound(a, 2))      # how many 2s
print(lower_bound(a, 6), upper_bound(a, 6))       # absent value
print(bisect_left(a, 2), bisect_right(a, 2))      # standard library agrees

1 4
3
5 5
1 4

The standard libraries already provide both. Python's bisect_left returns the insertion point before existing equal entries and bisect_right returns the point after them, according to the Python documentation. C++ offers std::lower_bound and std::upper_bound. The C++ reference says std::lower_bound needs a partitioned range and uses at most log2(N) + O(1) comparisons.

The search loop here uses a half-open interval, lo inclusive and hi exclusive, and hi = mid instead of mid - 1. Both styles are valid. Mixing them within one function is the most common source of off-by-one errors and endless loops.

What is binary search on the answer?

Binary search on the answer applies the same halving to a range of possible answers instead of an array. It works whenever a yes-or-no test is monotonic: false up to some value k and true from k onwards. The Competitive Programmer's Handbook describes this as finding the smallest valid solution using a function ok(x). The test runs O(log z) times, where z is the size of the search range.

Take a hypothetical depot that must ship six packages with weights 3, 2, 2, 4, 1 and 4 in the given order, using at most 3 days. What is the smallest daily truck capacity that works? The answer lies between the heaviest package (4) and the total weight (16). A capacity of 4 needs 5 days, 5 needs 4 days, and 6 needs 3 days, so more capacity never makes things worse and binary search applies.

def days_needed(weights, capacity):
    days, load = 1, 0
    for w in weights:
        if load + w > capacity:
            days, load = days + 1, 0
        load += w
    return days

def min_capacity(weights, max_days):
    lo, hi = max(weights), sum(weights)    # answer lies in [heaviest item, total]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(weights, mid) <= max_days:
            hi = mid                        # mid works: try smaller
        else:
            lo = mid + 1                    # mid too small
    return lo

weights = [3, 2, 2, 4, 1, 4]
print(min_capacity(weights, 3))             # smallest capacity that ships in 3 days
for c in range(4, 9):
    print(c, days_needed(weights, c))

6
4 5
5 4
6 3
7 3
8 3

The same pattern covers any monotonic test, such as the integer square root of a number: the largest x for which x times x is at most the number. If each test costs O(n), the whole search costs O(n log z), as the Handbook notes.

Can binary search work on an unsorted array?

No. Binary search discards half the range on the strength of one comparison, and that inference is valid only when order carries information. On unsorted data it can discard the half that holds the target. In C++, std::lower_bound on a range that is not partitioned is undefined behaviour. The sample reuses binary_search from the first Python block.

unsorted = [9, 3, 7, 1, 5]
print(5 in unsorted)                      # True: 5 is present
print(binary_search(unsorted, 5))         # -1: the halving rule discards the wrong half
print(binary_search(sorted(unsorted), 5)) # 2: works after sorting to [1, 3, 5, 7, 9]

True
-1
2

Sorting first costs O(n log n), so for a single lookup in unsorted data a plain O(n) scan is cheaper. Binary search pays off when the data is sorted once and searched many times. The sorting algorithms covered in this series explain what that first step costs.

What are the limits of binary search?

Binary search needs sorted data and constant-time access by index, which arrays and Python lists give. It is not a replacement for a hash table. The Python documentation says that for locating specific values dictionaries are more performant than the bisect module, which is better suited to searching ranges of values. Keeping a Python list sorted with insort also costs O(n) per insert, because the shifting of items dominates the O(log n) search.

Binary search is a good fit for lookups in a fixed sorted table, range queries ("how many values lie between a and b"), and the answer-search pattern above. The same left-smaller, right-larger idea is stored in a linked structure by the binary search trees discussed in binary tree traversal.

Where does binary search fit for working engineers?

The Competitive Programmer's Handbook advises using the standard library whenever possible, and Python's bisect and C++'s std::lower_bound already contain the loop. Understanding the halving idea still matters for monotonic tests that no library covers. The Forward Deployed Engineer (FDE) Cohort is a Leap by Masai programme for engineers with hands-on technical experience, run as an in-person start in Goa, an online build phase and an in-person hackathon in Bangalore for qualifying participants, covering production Python, APIs, cloud deployment, LLMs, retrieval, agents, security and client engagement.

Its content includes production-ready Python and data pipelines, APIs and access. Details are on the Forward Deployed Engineer cohort page.

Frequently asked questions

What is the time complexity of binary search?

Binary search runs in O(log n) time. It uses at most lg N + 1 comparisons on N sorted keys, so 1,000,000 elements need at most 20 steps. Space is O(1) for the loop version. A recursive version adds O(log n) call-stack space.

Can binary search work on an unsorted array?

No. Binary search relies on order to decide which half to discard, and on an unsorted array it can discard the half containing the target and wrongly report it missing. Sort the array first, or use a linear scan or a hash-based lookup for a one-off search.

What is binary search on answer?

Binary search on the answer halves a range of candidate answers instead of array positions. It applies when a yes-or-no test is monotonic, false for small values and true from some value onwards. Examples are the smallest capacity that meets a deadline, or the largest value satisfying a limit.

Why use lo + (hi - lo) / 2 instead of (lo + hi) / 2?

The sum lo + hi can exceed the largest 32-bit integer, 2,147,483,647, and overflow to a negative number. Bloch described this bug in Java's library in 2006. lo + (hi - lo) / 2 always stays within range. Python and JavaScript avoid the issue, but the safe form works everywhere.

What is the difference between lower bound and upper bound?

Lower bound returns the first index whose value is at least the target. Upper bound returns the first index whose value is greater than the target. For a value that occurs several times, they mark the start and one past the end of its run, and subtracting them gives the count.

Is binary search faster than a hash table lookup?

A hash table lookup is O(1) on average, against O(log n) for binary search, and the Python documentation advises dictionaries for locating specific values. Binary search keeps data ordered, so it supports range queries and nearest-value queries that a hash table cannot answer efficiently.

Next step

Practice by writing lower bound and search-on-the-answer solutions without looking at the code above, then test them against a plain scan on random data. If production Python and APIs are the next skills on the list, see the Forward Deployed Engineer cohort from Leap by Masai. The follow-up topic is time complexity and Big O notation for beginners.