Free explainer · Video · Code · Quiz

Binary Search

Find a value in a sorted array by checking the middle and throwing away the half that can't hold it — a million items in about 20 steps. Includes lowerBound, the form interviews actually ask for.

Difficulty: Easy
Time: O(log n)
Space: O(1)

Try it yourself Take the quiz

Try it yourself

Step through it at your own pace — this is Binary Search Animation, running right on the page.

Get this code

LiveBinary Search Animation

Loading the preview…

How it works

The idea, a worked example, and the traps to avoid.

The idea

Play "guess my number" between 1 and 100. A bad strategy is 1, 2, 3… A good one is to say 50, hear "higher", say 75, hear "lower", say 62… Each answer throws away half of what's left, so you never need more than 7 guesses.

Binary search is that game on a sorted array. Look at the middle element. If it's the target, done. If it's too small, the target can only be to its right; if it's too big, only to its left. Throw away the other half and repeat on what remains.

The one requirement is the word sorted. On unsorted data the "throw away half" step is a lie, and the search quietly returns wrong answers.

Walkthrough

Search for 12 in [1, 3, 5, 7, 9, 11, 13, 15] (indexes 0 to 7). We keep a range [lo, hi] where the target could still be.

Step	lo	hi	mid	sorted[mid]	Decision
1	0	7	3	7	7 < 12, so go right: `lo = 4`
2	4	7	5	11	11 < 12, so go right: `lo = 6`
3	6	7	6	13	13 > 12, so go left: `hi = 5`
4	6	5	–	–	`lo > hi`: the range is empty, return `-1`

Three looks at the array to prove 12 isn't among eight values. Searching for 11 instead stops at step 2 and returns 5. Notice where lo ended up in the failed search: index 6, exactly where 12 would be inserted to keep the array sorted. That's the next idea.

Why it works

The loop keeps one promise, the invariant: if the target is in the array, it is inside [lo, hi].

At the start the range is the whole array, so the promise holds.
When sorted[mid] < target, everything from lo to mid is at most sorted[mid], so it's too small too. Moving lo to mid + 1 keeps the promise. The other branch is the mirror image.
Every step removes at least mid itself, so the range strictly shrinks and the loop must end.

When the range is empty, the promise says the target isn't there. That's the whole proof.

lowerBound: the version you'll actually use

lowerBound(sorted, target) returns the first index whose value is ≥ target. If every value is smaller, it returns sorted.length. It uses a half-open range [lo, hi) with a different promise: everything before lo is < target, and everything from hi on is ≥ target. When lo and hi meet, that meeting point is the answer.

It answers more questions than plain search:

First occurrence of a value with duplicates: lowerBound(a, x), then check a[i] === x.
How many times x appears: lowerBound(a, x + 1) - lowerBound(a, x).
Where to insert x to keep the array sorted.

It's in every standard library: Python's bisect.bisect_left, C++'s std::lower_bound.

Complexity

Each step halves the range: n, n/2, n/4… down to 1. That takes about log₂ n steps, so the time is O(log n).

n	Steps (worst case)
1,000	10
1,000,000	20
1,000,000,000	30

Space is O(1). The iterative version only keeps lo, hi and mid. A recursive version would use O(log n) stack for the same work.

Common bugs

Mixing the two range styles. while (lo <= hi) goes with hi = n - 1 and hi = mid - 1 (closed range). while (lo < hi) goes with hi = n and hi = mid (half-open). Mix them and you skip the last element or loop forever. Pick one style per function and say which in a comment.
lo = mid instead of lo = mid + 1. When hi = lo + 1, mid equals lo, nothing moves, and the loop never ends.
Integer overflow in (lo + hi) / 2. With 32-bit ints, lo + hi can pass 2,147,483,647 and turn negative. This exact bug sat in Java's Arrays.binarySearch for about nine years before anyone noticed. lo + (hi - lo) / 2 can't overflow. JavaScript numbers and Python integers don't overflow here, but the safe form costs nothing, so make it a habit.
Expecting the first match. With duplicates, the classic search returns some matching index. Use lowerBound when you need the first one.

When to use it (and when not)

Use it when data is sorted and you look things up many times, or when you can search over a yes/no question that flips only once, like "can we finish in t days?". That's called binary search on the answer.

Skip it when:

The data is unsorted and you only search once. Sorting costs O(n log n), more than a single O(n) scan.
The data changes all the time. A balanced tree or a hash set fits better.
You only need exact lookups. A hash map does them in O(1) on average.
The data is a linked list. You can't jump to the middle.

Interview variations

Search in a rotated sorted array ([4, 5, 6, 7, 0, 1, 2]). At any mid, one of the two halves is still sorted. Check whether the target lies inside that sorted half's range; if not, go to the other half. Still O(log n).
First and last position of a value. The first is lowerBound(a, x). The last is lowerBound(a, x + 1) - 1. Two searches, no linear scan.
Binary search on the answer. "Smallest ship capacity that delivers all packages in D days", "integer square root", "Koko eating bananas". There's no array, but feasible(answer) is false…false, true…true. Search for the first true with exactly the lowerBound loop.

Code

The same algorithm, step for step, in 4 languages.

JavaScript

// Binary search on an array sorted in ascending order.
// Every step looks at the middle of the range that can still hold the answer
// and throws away the half that cannot — so n items take about log2(n) steps.

/**
 * Finds `target` in `sorted`.
 * With duplicates it returns one of the matching indexes, not necessarily the first —
 * use `lowerBound` when you need the first one.
 *
 * @param {number[]} sorted values in ascending order
 * @param {number} target the value to look for
 * @returns {number} an index i with sorted[i] === target, or -1 if there is none
 */
export function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1; // the answer, if any, is inside [lo, hi] (both ends included)

  while (lo <= hi) {
    // Same as (lo + hi) / 2, but lo + hi can overflow a fixed-size integer in other languages.
    const mid = lo + Math.floor((hi - lo) / 2);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) {
      lo = mid + 1; // sorted[lo..mid] are all too small
    } else {
      hi = mid - 1; // sorted[mid..hi] are all too big
    }
  }
  return -1; // the range is empty: target is not in the array
}

/**
 * The first index whose value is >= `target` — where `target` would be inserted to keep the
 * array sorted. Returns `sorted.length` when every value is smaller than `target`.
 *
 * @param {number[]} sorted values in ascending order
 * @param {number} target the value to look for
 * @returns {number} an index in [0, sorted.length]
 */
export function lowerBound(sorted, target) {
  let lo = 0;
  let hi = sorted.length; // the answer is inside [lo, hi) — hi itself is a valid answer

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    if (sorted[mid] < target) {
      lo = mid + 1; // mid and everything before it are too small
    } else {
      hi = mid; // mid might be the answer, so keep it in the range
    }
  }
  return lo; // lo === hi: the first index whose value is >= target
}

# Binary search on a list sorted in ascending order.
# Every step looks at the middle of the range that can still hold the answer
# and throws away the half that cannot — so n items take about log2(n) steps.
from typing import Sequence


def binary_search(sorted_values: Sequence[int], target: int) -> int:
    """Return an index i with sorted_values[i] == target, or -1 if there is none.

    With duplicates it returns one of the matching indexes, not necessarily
    the first — use lower_bound when you need the first one.
    """
    lo = 0
    hi = len(sorted_values) - 1  # the answer, if any, is inside [lo, hi] (both ends included)

    while lo <= hi:
        # Python integers never overflow, but this form is safe in every language.
        mid = lo + (hi - lo) // 2

        if sorted_values[mid] == target:
            return mid
        if sorted_values[mid] < target:
            lo = mid + 1  # sorted_values[lo..mid] are all too small
        else:
            hi = mid - 1  # sorted_values[mid..hi] are all too big
    return -1  # the range is empty: target is not in the list


def lower_bound(sorted_values: Sequence[int], target: int) -> int:
    """Return the first index whose value is >= target.

    That is where target would be inserted to keep the list sorted, so it is
    len(sorted_values) when every value is smaller (same as bisect.bisect_left).
    """
    lo = 0
    hi = len(sorted_values)  # the answer is inside [lo, hi) — hi itself is a valid answer

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if sorted_values[mid] < target:
            lo = mid + 1  # mid and everything before it are too small
        else:
            hi = mid  # mid might be the answer, so keep it in the range
    return lo  # lo == hi: the first index whose value is >= target

/**
 * Binary search on an array sorted in ascending order.
 * Every step looks at the middle of the range that can still hold the answer
 * and throws away the half that cannot — so n items take about log2(n) steps.
 */
public final class BinarySearch {
    private BinarySearch() {
    }

    /**
     * Returns an index i with sorted[i] == target, or -1 if there is none.
     * With duplicates it returns one of the matching indexes, not necessarily the first —
     * use {@link #lowerBound} when you need the first one.
     */
    public static int binarySearch(int[] sorted, int target) {
        int lo = 0;
        int hi = sorted.length - 1; // the answer, if any, is inside [lo, hi] (both ends included)

        while (lo <= hi) {
            // (lo + hi) / 2 overflows when lo + hi > Integer.MAX_VALUE; this form never does.
            int mid = lo + (hi - lo) / 2;

            if (sorted[mid] == target) {
                return mid;
            }
            if (sorted[mid] < target) {
                lo = mid + 1; // sorted[lo..mid] are all too small
            } else {
                hi = mid - 1; // sorted[mid..hi] are all too big
            }
        }
        return -1; // the range is empty: target is not in the array
    }

    /**
     * Returns the first index whose value is >= target — where target would be inserted to keep
     * the array sorted. Returns sorted.length when every value is smaller than target.
     */
    public static int lowerBound(int[] sorted, int target) {
        int lo = 0;
        int hi = sorted.length; // the answer is inside [lo, hi) — hi itself is a valid answer

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            if (sorted[mid] < target) {
                lo = mid + 1; // mid and everything before it are too small
            } else {
                hi = mid; // mid might be the answer, so keep it in the range
            }
        }
        return lo; // lo == hi: the first index whose value is >= target
    }
}

// Binary search on a vector sorted in ascending order.
// Every step looks at the middle of the range that can still hold the answer
// and throws away the half that cannot — so n items take about log2(n) steps.
// (The standard library has it too: std::binary_search and std::lower_bound in <algorithm>.)
#include <vector>

// Returns an index i with sorted[i] == target, or -1 if there is none.
// With duplicates it returns one of the matching indexes, not necessarily the first —
// use lowerBound when you need the first one.
int binarySearch(const std::vector<int>& sorted, int target) {
    int lo = 0;
    int hi = static_cast<int>(sorted.size()) - 1;  // the answer, if any, is inside [lo, hi]

    while (lo <= hi) {
        // (lo + hi) / 2 overflows when lo + hi > INT_MAX; this form never does.
        int mid = lo + (hi - lo) / 2;

        if (sorted[mid] == target) {
            return mid;
        }
        if (sorted[mid] < target) {
            lo = mid + 1;  // sorted[lo..mid] are all too small
        } else {
            hi = mid - 1;  // sorted[mid..hi] are all too big
        }
    }
    return -1;  // the range is empty: target is not in the vector
}

// Returns the first index whose value is >= target — where target would be inserted to keep
// the vector sorted. Returns sorted.size() when every value is smaller than target.
int lowerBound(const std::vector<int>& sorted, int target) {
    int lo = 0;
    int hi = static_cast<int>(sorted.size());  // the answer is inside [lo, hi) — hi itself is valid

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (sorted[mid] < target) {
            lo = mid + 1;  // mid and everything before it are too small
        } else {
            hi = mid;  // mid might be the answer, so keep it in the range
        }
    }
    return lo;  // lo == hi: the first index whose value is >= target
}

Ask about this algorithm

Stuck on a step? Ask for another example or why it works.

Test yourself

10 quick questions to check it stuck.

Q1 · binarySearch looks for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Which indexes does the loop look at, in order?

Take the quiz

Take it further

Animation
Binary Search Animation
A step-by-step binary search with gliding lo / mid / hi pointers, ready for your lessons, slides and posts
Free