Binary search

In plain words

You look for a word in a printed dictionary. You do not read each page. You open the book at the middle. If your word comes before the words on that page, you keep the first half. If it comes after, you keep the second half. You do the same step again on the half that you keep. Each step removes half of the pages, so you find the word after a small number of steps.

Binary search does this on a sorted array. It compares the key with the middle item. The result of the comparison tells which half can hold the key. The algorithm stops when it finds the key, or when no items are left.

See it run

BINARY-SEARCH(A, x)
1lo ← 0, hi ← n ▷ the range is A[lo .. hi − 1]
2while lo < hi do
3mid ← lo + ⌊(hi − lo) / 2⌋ ▷ no overflow, unlike ⌊(lo + hi) / 2⌋
4if A[mid] < x then
5lo ← mid + 1 ▷ x is not in A[lo .. mid]
6else if A[mid] > x then
7hi ← mid ▷ x is not in A[mid .. hi − 1]
8else return mid
9return NIL

0 / 0 Speed Input

Use your own input

Type the input as JSON, in the same form as a preset.

Open the full player

The problem

The input is an array $A[0 \ldots n-1]$ of $n$ items in non-decreasing order, and a key $x$ . The output is an index $i$ with $A[i] = x$ , or NIL when no item is equal to $x$ . This is the problem search in a sorted array. When the array has more than one copy of $x$ , any index of a copy is a correct answer.

The algorithm only compares items. It does not do arithmetic on them. So it works for numbers, strings and any other type with a total order.

The algorithm

The algorithm keeps a range of indices $[lo, hi)$ . The key can only be at an index in this range. At the start, the range is the full array.

BINARY-SEARCH(A, x)
1lo ← 0, hi ← n ▷ the range is A[lo .. hi − 1]
2while lo < hi do
3mid ← lo + ⌊(hi − lo) / 2⌋ ▷ no overflow, unlike ⌊(lo + hi) / 2⌋
4if A[mid] < x then
5lo ← mid + 1 ▷ x is not in A[lo .. mid]
6else if A[mid] > x then
7hi ← mid ▷ x is not in A[mid .. hi − 1]
8else return mid
9return NIL

Line L3 picks the middle of the range. Lines L4 to L8 compare $A[mid]$ with $x$ . If $A[mid] < x$ , then each item at an index of $mid$ or less is less than $x$ , because the array is sorted. So line L5 removes these indices from the range. Line L7 does the same on the other side. Line L9 runs when the range is empty.

Example

The array is $A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]$ , with $n = 10$ . A search for $x = 23$ takes one step. The first middle item is $A[5] = 23$ , so the algorithm returns 5.

A search for $x = 30$ takes four steps:

step	lo	hi	mid	$A[mid]$	result
1	0	10	5	23	$23 < 30$ , so $lo \gets 6$
2	6	10	8	72	$72 > 30$ , so $hi \gets 8$
3	6	8	7	56	$56 > 30$ , so $hi \gets 7$
4	6	7	6	38	$38 > 30$ , so $hi \gets 6$

Now $lo = hi = 6$ . The range is empty, so the algorithm returns NIL. The index 6 is the place where 30 can go to keep the array sorted.

Correctness

The proof uses a loop invariant. Before each test of line L2, this statement is true:

If $x$ is in $A$ , then $x$ is in $A[lo \ldots hi-1]$ .

At the start, the range is the full array, so the statement is true. Each step keeps it true, because lines L5 and L7 only remove indices that cannot hold $x$ . Each step also makes the range smaller, because $lo \le mid < hi$ . So the loop stops. When line L8 returns, $A[mid] = x$ . When line L9 returns, the range is empty, and by the invariant $x$ is not in $A$ . The full proof is below.

Proof: Binary search returns an index of x, or NIL when x is not in Afull

Let $A[0 \ldots n-1]$ be sorted in non-decreasing order. We prove three facts about BINARY-SEARCH $(A, x)$ .

Invariant. Before each test of line L2, these statements are true:

$0 \le lo \le hi \le n$ .
For each index $i < lo$ , $A[i] < x$ .
For each index $i \ge hi$ , $A[i] > x$ .

Start. Line L1 sets $lo = 0$ and $hi = n$ . Statement 1 is true. Statements 2 and 3 are true because no index is less than 0 and no index is at least $n$ .

Step. Assume that the statements are true and that $lo < hi$ . Line L3 sets $mid = lo + \lfloor (hi - lo)/2 \rfloor$ . Because $hi - lo \ge 1$ , we have $lo \le mid < hi$ .

If $A[mid] < x$ , line L5 sets $lo' = mid + 1$ . For each $i$ with $lo \le i \le mid$ , $A[i] \le A[mid] < x$ because $A$ is sorted. With statement 2 for the old $lo$ , each $i < lo'$ has $A[i] < x$ . Also $lo' \le hi$ because $mid < hi$ .
If $A[mid] > x$ , line L7 sets $hi' = mid$ . For each $i$ with $mid \le i < hi$ , $A[i] \ge A[mid] > x$ . With statement 3 for the old $hi$ , each $i \ge hi'$ has $A[i] > x$ . Also $lo \le hi'$ because $lo \le mid$ .
Otherwise $A[mid] = x$ , and line L8 returns.

So the statements are true before the next test of line L2.

Termination. The value $hi - lo$ is a non-negative integer by statement 1. In each step that does not return, it becomes smaller: in the first case $hi - (mid + 1) < hi - lo$ because $mid \ge lo$ , and in the second case $mid - lo < hi - lo$ because $mid < hi$ . A non-negative integer cannot become smaller for ever. So the loop stops.

Result. If line L8 returns $mid$ , then $A[mid] = x$ and $0 \le mid < n$ , so the result is correct. If line L9 returns NIL, then $lo \ge hi$ , and by statement 1, $lo = hi$ . By statements 2 and 3, each index $i$ has $A[i] < x$ or $A[i] > x$ . So no item of $A$ is equal to $x$ , and NIL is correct. $\blacksquare$

The number of steps. Let $k = hi - lo$ before a step. The new size is $\lfloor (k-1)/2 \rfloor$ or $\lceil (k-1)/2 \rceil$ , and both are at most $\lfloor k/2 \rfloor$ . Then after $t$ steps the size is at most $\lfloor n/2^t \rfloor$ , which is 0 when $t = \lfloor \lg n \rfloor + 1$ . So the loop runs at most $\lfloor \lg n \rfloor + 1$ times.

All proofs on one page

Complexity

Let $k$ be the size $hi - lo$ of the range. One step of the loop makes the new size at most $\lfloor k/2 \rfloor$ . So after $t$ steps the size is at most $\lfloor n / 2^t \rfloor$ , and the loop runs at most $\lfloor \lg n \rfloor + 1$ times. Each step does one three-way comparison of $A[mid]$ with $x$ , and a fixed number of other operations.

The time in the worst case is $\Theta(\log n)$ . The worst case is a key that is not in the array.
The time in the best case is $\Theta(1)$ . The key is the first middle item.
The extra space is $\Theta(1)$ : three indices.

In the comparison model, each algorithm for this problem needs $\lceil \lg(n+1) \rceil$ three-way comparisons in the worst case. The argument uses a decision tree: the tree must tell apart the $n$ positions of $x$ and the case "not found". Because $\lfloor \lg n \rfloor + 1 = \lceil \lg(n+1) \rceil$ , binary search is optimal in this model.

Variants and improvements

Lower bound. Return the first index $i$ with $A[i] \ge x$ . This answers "where does $x$ go" and "how many items are less than $x$ ". Remove line L8, change line L6 to "else $hi \gets mid$ ", and return $lo$ at line L9. The C++ function std::lower_bound and the Python function bisect.bisect_left do this.
Upper bound. Return the first index $i$ with $A[i] > x$ . The number of copies of $x$ is the upper bound minus the lower bound.
Search on the answer. Use the same loop on any predicate that is false and then true over a range of integers. This finds the smallest value that satisfies the predicate.
Exponential search. When $n$ is not known, or the key is near the start, test the indices $1, 2, 4, 8, \ldots$ first. Then do a binary search in the last interval. The time is $O(\log i)$ for a key at index $i$ .
Interpolation search. Guess the index from the values, as a person does with a phone book. On uniform data the average time is $O(\log \log n)$ , but the worst case is $O(n)$ .

When to use it

Use binary search when the data is sorted and does not change often, and you search it many times. If the data changes often, a balanced search tree or a hash table is better. A hash table also answers a search in $O(1)$ expected time, but it cannot answer "which is the next larger item". If you search an array only once, a linear scan in $O(n)$ costs less than a sort in $O(n \log n)$ followed by a binary search.

Pitfalls

Overflow. The expression $\lfloor (lo + hi)/2 \rfloor$ can overflow a fixed-size integer when the array is very large. This bug was in the Java library for nine years. Use $lo + \lfloor (hi - lo)/2 \rfloor$ , as line L3 does.
An infinite loop. With a closed range $[lo, hi]$ , the update " $lo \gets mid$ " can keep the range the same size. Each update must remove $mid$ , or the range must be half-open as here.
An off-by-one error. Decide if $hi$ is in the range or not, and use the same rule in each line.
Unsorted input. On an array that is not sorted, the result has no meaning. The algorithm does not detect this.

Implementations

Each implementation follows the pseudocode above. A comment @line links a line of code to a line of the pseudocode. Point at a line of the pseudocode to see the matching code. The build runs the native tests of each language.

binary_search.pytests passPage Raw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

from collections.abc import Sequence
from typing import Protocol, TypeVar


class Ordered(Protocol):
    def __lt__(self, other: "Ordered", /) -> bool: ...


T = TypeVar("T", bound=Ordered)


def binary_search(a: Sequence[T], x: T) -> int:
    """Return an index i with a[i] == x, or -1 when x is not in a. The list a must be sorted."""
    lo, hi = 0, len(a)  # @line L1
    while lo < hi:  # @line L2
        mid = lo + (hi - lo) // 2  # @line L3
        if a[mid] < x:  # @line L4
            lo = mid + 1  # @line L5
        elif x < a[mid]:  # @line L6
            hi = mid  # @line L7
        else:
            return mid  # @line L8
    return -1  # @line L9

test_binary_search.py 43 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

import random

from binary_search import binary_search


def test_examples() -> None:
    a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    assert binary_search(a, 23) == 5
    assert binary_search(a, 2) == 0
    assert binary_search(a, 91) == 9
    assert binary_search(a, 30) == -1
    assert binary_search(a, 1) == -1
    assert binary_search(a, 100) == -1


def test_empty_and_single() -> None:
    assert binary_search([], 1) == -1
    assert binary_search([7], 7) == 0
    assert binary_search([7], 3) == -1


def test_duplicates() -> None:
    a = [1, 3, 3, 3, 5]
    assert a[binary_search(a, 3)] == 3


def test_strings() -> None:
    assert binary_search(["ant", "bee", "cat"], "bee") == 1


def test_random_against_linear_scan() -> None:
    rng = random.Random(2150)
    for _ in range(2000):
        a = sorted(rng.randint(-20, 20) for _ in range(rng.randint(0, 30)))
        x = rng.randint(-25, 25)
        i = binary_search(a, x)
        if x in a:
            assert 0 <= i < len(a) and a[i] == x
        else:
            assert i == -1

binary_search.hpptests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

#pragma once

#include <cstddef>
#include <optional>
#include <span>

namespace algo {

// binary_search returns an index i with a[i] == x, or nothing when x is not in a. The span must be sorted.
template <typename T>
std::optional<std::size_t> binary_search(std::span<const T> a, const T& x) {
    std::size_t lo = 0, hi = a.size();          // @line L1
    while (lo < hi) {                           // @line L2
        std::size_t mid = lo + (hi - lo) / 2;   // @line L3
        if (a[mid] < x) {                       // @line L4
            lo = mid + 1;                       // @line L5
        } else if (x < a[mid]) {                // @line L6
            hi = mid;                           // @line L7
        } else {
            return mid;                         // @line L8
        }
    }
    return std::nullopt;                        // @line L9
}

}  // namespace algo

test_binary_search.cpp 41 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "binary_search.hpp"

int main() {
    const std::vector<int> a{2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    std::span<const int> s(a);
    assert(algo::binary_search(s, 23) == 5);
    assert(algo::binary_search(s, 2) == 0);
    assert(algo::binary_search(s, 91) == 9);
    assert(!algo::binary_search(s, 30));
    assert(!algo::binary_search(s, 1));
    assert(!algo::binary_search(s, 100));
    assert(!algo::binary_search(std::span<const int>{}, 1));

    const std::vector<std::string> w{"ant", "bee", "cat"};
    assert(algo::binary_search(std::span<const std::string>(w), std::string("bee")) == 1);

    std::mt19937 rng(2150);
    for (int t = 0; t < 2000; t++) {
        std::vector<int> b(rng() % 31);
        for (auto& v : b) v = static_cast<int>(rng() % 41) - 20;
        std::ranges::sort(b);
        int x = static_cast<int>(rng() % 51) - 25;
        auto got = algo::binary_search(std::span<const int>(b), x);
        if (std::ranges::find(b, x) != b.end()) {
            assert(got && b[*got] == x);
        } else {
            assert(!got);
        }
    }
    std::cout << "ok\n";
}

BinarySearch.javatests failPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

/** Binary search in a sorted array. */
public final class BinarySearch {
    private BinarySearch() {}

    /** Returns an index i with a[i] == x, or -1 when x is not in a. The array must be sorted. */
    public static int search(long[] a, long x) {
        int lo = 0, hi = a.length;                // @line L1
        while (lo < hi) {                         // @line L2
            int mid = lo + (hi - lo) / 2;         // @line L3
            if (a[mid] < x) {                     // @line L4
                lo = mid + 1;                     // @line L5
            } else if (a[mid] > x) {              // @line L6
                hi = mid;                         // @line L7
            } else {
                return mid;                       // @line L8
            }
        }
        return -1;                                // @line L9
    }

    /** The same search for any type with a natural order. */
    public static <T extends Comparable<? super T>> int search(T[] a, T x) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int c = a[mid].compareTo(x);
            if (c < 0) {
                lo = mid + 1;
            } else if (c > 0) {
                hi = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

BinarySearchTest.java 43 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

import static org.junit.jupiter.api.Assertions.assertEquals;

import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;

class BinarySearchTest {
    @Test
    void examples() {
        long[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        assertEquals(5, BinarySearch.search(a, 23));
        assertEquals(0, BinarySearch.search(a, 2));
        assertEquals(9, BinarySearch.search(a, 91));
        assertEquals(-1, BinarySearch.search(a, 30));
        assertEquals(-1, BinarySearch.search(a, 1));
        assertEquals(-1, BinarySearch.search(a, 100));
    }

    @Test
    void edges() {
        assertEquals(-1, BinarySearch.search(new long[0], 1));
        assertEquals(0, BinarySearch.search(new long[] {7}, 7));
        assertEquals(1, BinarySearch.search(new String[] {"ant", "bee", "cat"}, "bee"));
    }

    @Test
    void randomAgainstLinearScan() {
        Random rng = new Random(2150);
        for (int t = 0; t < 2000; t++) {
            long[] a = new long[rng.nextInt(31)];
            for (int i = 0; i < a.length; i++) a[i] = rng.nextInt(41) - 20;
            Arrays.sort(a);
            long x = rng.nextInt(51) - 25;
            int got = BinarySearch.search(a, x);
            boolean found = Arrays.stream(a).anyMatch(v -> v == x);
            if (found) assertEquals(x, a[got]);
            else assertEquals(-1, got);
        }
    }
}

binary_search.ctests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

#include "binary_search.h"

ptrdiff_t binary_search(const int64_t *a, size_t n, int64_t x) {
    size_t lo = 0, hi = n;                 // @line L1
    while (lo < hi) {                      // @line L2
        size_t mid = lo + (hi - lo) / 2;   // @line L3
        if (a[mid] < x) {                  // @line L4
            lo = mid + 1;                  // @line L5
        } else if (a[mid] > x) {           // @line L6
            hi = mid;                      // @line L7
        } else {
            return (ptrdiff_t)mid;         // @line L8
        }
    }
    return -1;                             // @line L9
}

binary_search.h 13 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H

#include <stddef.h>
#include <stdint.h>

// binary_search returns an index i with a[i] == x, or -1 when x is not in a[0..n-1]. The array must be sorted.
ptrdiff_t binary_search(const int64_t *a, size_t n, int64_t x);

#endif

test_binary_search.c 43 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "binary_search.h"

static int cmp(const void *p, const void *q) {
    int64_t a = *(const int64_t *)p, b = *(const int64_t *)q;
    return (a > b) - (a < b);
}

int main(void) {
    const int64_t a[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    assert(binary_search(a, 10, 23) == 5);
    assert(binary_search(a, 10, 2) == 0);
    assert(binary_search(a, 10, 91) == 9);
    assert(binary_search(a, 10, 30) == -1);
    assert(binary_search(a, 10, 1) == -1);
    assert(binary_search(a, 10, 100) == -1);
    assert(binary_search(NULL, 0, 1) == -1);

    srand(2150);
    int64_t b[30];
    for (int t = 0; t < 2000; t++) {
        size_t n = (size_t)(rand() % 31);
        for (size_t i = 0; i < n; i++) b[i] = rand() % 41 - 20;
        qsort(b, n, sizeof b[0], cmp);
        int64_t x = rand() % 51 - 25;
        ptrdiff_t got = binary_search(b, n, x);
        int found = 0;
        for (size_t i = 0; i < n; i++) found |= b[i] == x;
        if (found) {
            assert(got >= 0 && (size_t)got < n && b[got] == x);
        } else {
            assert(got == -1);
        }
    }
    puts("ok");
    return 0;
}

BinarySearch.csPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

namespace Algorithm;

/// <summary>Binary search in a sorted array.</summary>
public static class BinarySearch
{
    /// <summary>Returns an index i with a[i] == x, or -1 when x is not in a. The array must be sorted.</summary>
    public static int Search<T>(ReadOnlySpan<T> a, T x) where T : IComparable<T>
    {
        int lo = 0, hi = a.Length;              // @line L1
        while (lo < hi)                         // @line L2
        {
            int mid = lo + (hi - lo) / 2;       // @line L3
            int c = a[mid].CompareTo(x);
            if (c < 0)                          // @line L4
            {
                lo = mid + 1;                   // @line L5
            }
            else if (c > 0)                     // @line L6
            {
                hi = mid;                       // @line L7
            }
            else
            {
                return mid;                     // @line L8
            }
        }
        return -1;                              // @line L9
    }
}

BinarySearchTests.cs 45 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

using Algorithm;
using Xunit;

public class BinarySearchTests
{
    [Theory]
    [InlineData(23, 5)]
    [InlineData(2, 0)]
    [InlineData(91, 9)]
    [InlineData(30, -1)]
    [InlineData(1, -1)]
    [InlineData(100, -1)]
    public void Examples(long x, int want)
    {
        long[] a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
        Assert.Equal(want, BinarySearch.Search<long>(a, x));
    }

    [Fact]
    public void Edges()
    {
        Assert.Equal(-1, BinarySearch.Search<long>(Array.Empty<long>(), 1));
        Assert.Equal(0, BinarySearch.Search<long>(new long[] { 7 }, 7));
        Assert.Equal(1, BinarySearch.Search<string>(new[] { "ant", "bee", "cat" }, "bee"));
    }

    [Fact]
    public void RandomAgainstLinearScan()
    {
        var rng = new Random(2150);
        for (int t = 0; t < 2000; t++)
        {
            var a = new long[rng.Next(31)];
            for (int i = 0; i < a.Length; i++) a[i] = rng.Next(41) - 20;
            Array.Sort(a);
            long x = rng.Next(51) - 25;
            int got = BinarySearch.Search<long>(a, x);
            if (Array.IndexOf(a, x) >= 0) Assert.Equal(x, a[got]);
            else Assert.Equal(-1, got);
        }
    }
}

binarySearch.jstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

/**
 * Returns an index i with a[i] === x, or -1 when x is not in a. The array must be sorted.
 * @template T
 * @param {readonly T[]} a
 * @param {T} x
 * @returns {number}
 */
export function binarySearch(a, x) {
  let lo = 0, hi = a.length; // @line L1
  while (lo < hi) { // @line L2
    const mid = lo + ((hi - lo) >> 1); // @line L3
    if (a[mid] < x) { // @line L4
      lo = mid + 1; // @line L5
    } else if (a[mid] > x) { // @line L6
      hi = mid; // @line L7
    } else {
      return mid; // @line L8
    }
  }
  return -1; // @line L9
}

binarySearch.test.js 37 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

import { test } from "node:test";
import assert from "node:assert/strict";
import { binarySearch } from "./binarySearch.js";

test("examples", () => {
  const a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
  assert.equal(binarySearch(a, 23), 5);
  assert.equal(binarySearch(a, 2), 0);
  assert.equal(binarySearch(a, 91), 9);
  assert.equal(binarySearch(a, 30), -1);
  assert.equal(binarySearch(a, 1), -1);
  assert.equal(binarySearch(a, 100), -1);
});

test("edges", () => {
  assert.equal(binarySearch([], 1), -1);
  assert.equal(binarySearch([7], 7), 0);
  assert.equal(binarySearch(["ant", "bee", "cat"], "bee"), 1);
});

test("random against a linear scan", () => {
  let s = 2150;
  const next = (m) => {
    s = (Math.imul(s, 1103515245) + 12345) >>> 0;
    return (s >>> 8) % m;
  };
  for (let t = 0; t < 2000; t++) {
    const a = Array.from({ length: next(31) }, () => next(41) - 20).sort((p, q) => p - q);
    const x = next(51) - 25;
    const i = binarySearch(a, x);
    if (a.includes(x)) assert.equal(a[i], x);
    else assert.equal(i, -1);
  }
});

binarySearch.tstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

/** Returns an index i with a[i] === x, or -1 when x is not in a. The array must be sorted. */
export function binarySearch<T>(a: readonly T[], x: T): number {
  let lo = 0, hi = a.length; // @line L1
  while (lo < hi) { // @line L2
    const mid = lo + ((hi - lo) >> 1); // @line L3
    if (a[mid] < x) { // @line L4
      lo = mid + 1; // @line L5
    } else if (a[mid] > x) { // @line L6
      hi = mid; // @line L7
    } else {
      return mid; // @line L8
    }
  }
  return -1; // @line L9
}

binarySearch.test.ts 37 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

import { test } from "node:test";
import assert from "node:assert/strict";
import { binarySearch } from "./binarySearch.ts";

test("examples", () => {
  const a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
  assert.equal(binarySearch(a, 23), 5);
  assert.equal(binarySearch(a, 2), 0);
  assert.equal(binarySearch(a, 91), 9);
  assert.equal(binarySearch(a, 30), -1);
  assert.equal(binarySearch(a, 1), -1);
  assert.equal(binarySearch(a, 100), -1);
});

test("edges", () => {
  assert.equal(binarySearch([], 1), -1);
  assert.equal(binarySearch([7], 7), 0);
  assert.equal(binarySearch(["ant", "bee", "cat"], "bee"), 1);
});

test("random against a linear scan", () => {
  let s = 2150;
  const next = (m: number): number => {
    s = (Math.imul(s, 1103515245) + 12345) >>> 0;
    return (s >>> 8) % m;
  };
  for (let t = 0; t < 2000; t++) {
    const a = Array.from({ length: next(31) }, () => next(41) - 20).sort((p, q) => p - q);
    const x = next(51) - 25;
    const i = binarySearch(a, x);
    if (a.includes(x)) assert.equal(a[i], x);
    else assert.equal(i, -1);
  }
});

binary_search.gotests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

// Package binarysearch finds a key in a sorted slice.
package binarysearch

import "cmp"

// Search returns an index i with a[i] == x, or -1 when x is not in a. The slice a must be sorted.
func Search[T cmp.Ordered](a []T, x T) int {
	lo, hi := 0, len(a) // @line L1
	for lo < hi {       // @line L2
		mid := lo + (hi-lo)/2 // @line L3
		switch {
		case a[mid] < x: // @line L4
			lo = mid + 1 // @line L5
		case a[mid] > x: // @line L6
			hi = mid // @line L7
		default:
			return mid // @line L8
		}
	}
	return -1 // @line L9
}

binary_search_test.go 55 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

package binarysearch

import (
	"math/rand/v2"
	"slices"
	"testing"
)

func TestExamples(t *testing.T) {
	a := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	for _, c := range []struct{ x, want int }{{23, 5}, {2, 0}, {91, 9}, {30, -1}, {1, -1}, {100, -1}} {
		if got := Search(a, c.x); got != c.want {
			t.Errorf("Search(a, %d) = %d, want %d", c.x, got, c.want)
		}
	}
}

func TestEdges(t *testing.T) {
	if got := Search([]int{}, 1); got != -1 {
		t.Errorf("empty: got %d", got)
	}
	if got := Search([]int{7}, 7); got != 0 {
		t.Errorf("single: got %d", got)
	}
	if got := Search([]string{"ant", "bee", "cat"}, "bee"); got != 1 {
		t.Errorf("strings: got %d", got)
	}
	a := []int{1, 3, 3, 3, 5}
	if i := Search(a, 3); i < 0 || a[i] != 3 {
		t.Errorf("duplicates: got %d", i)
	}
}

func TestRandom(t *testing.T) {
	r := rand.New(rand.NewPCG(2150, 0))
	for range 2000 {
		a := make([]int, r.IntN(31))
		for i := range a {
			a[i] = r.IntN(41) - 20
		}
		slices.Sort(a)
		x := r.IntN(51) - 25
		i := Search(a, x)
		if slices.Contains(a, x) {
			if i < 0 || i >= len(a) || a[i] != x {
				t.Fatalf("Search(%v, %d) = %d", a, x, i)
			}
		} else if i != -1 {
			t.Fatalf("Search(%v, %d) = %d, want -1", a, x, i)
		}
	}
}

binary_search.rstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

//! Binary search in a sorted slice.

use std::cmp::Ordering;

/// Returns an index `i` with `a[i] == *x`, or `None` when `x` is not in `a`. The slice must be sorted.
pub fn binary_search<T: Ord>(a: &[T], x: &T) -> Option<usize> {
    let (mut lo, mut hi) = (0, a.len()); // @line L1
    while lo < hi {
        // @line L2
        let mid = lo + (hi - lo) / 2; // @line L3
        match a[mid].cmp(x) {
            Ordering::Less => lo = mid + 1,  // @line L4 L5
            Ordering::Greater => hi = mid,   // @line L6 L7
            Ordering::Equal => return Some(mid), // @line L8
        }
    }
    None // @line L9
}

binary_search_test.rs 45 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

use algo_binary_search::binary_search;

#[test]
fn examples() {
    let a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
    assert_eq!(binary_search(&a, &23), Some(5));
    assert_eq!(binary_search(&a, &2), Some(0));
    assert_eq!(binary_search(&a, &91), Some(9));
    assert_eq!(binary_search(&a, &30), None);
    assert_eq!(binary_search(&a, &1), None);
    assert_eq!(binary_search(&a, &100), None);
}

#[test]
fn edges() {
    let empty: [i32; 0] = [];
    assert_eq!(binary_search(&empty, &1), None);
    assert_eq!(binary_search(&[7], &7), Some(0));
    assert_eq!(binary_search(&["ant", "bee", "cat"], &"bee"), Some(1));
    let a = [1, 3, 3, 3, 5];
    assert_eq!(a[binary_search(&a, &3).unwrap()], 3);
}

#[test]
fn random_against_linear_scan() {
    // A small linear congruential generator, so that the test needs no crate.
    let mut s: u64 = 2150;
    let mut next = |m: u64| {
        s = s.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        (s >> 33) % m
    };
    for _ in 0..2000 {
        let n = next(31) as usize;
        let mut a: Vec<i64> = (0..n).map(|_| next(41) as i64 - 20).collect();
        a.sort();
        let x = next(51) as i64 - 25;
        match binary_search(&a, &x) {
            Some(i) => assert_eq!(a[i], x),
            None => assert!(!a.contains(&x)),
        }
    }
}

BinarySearch.ktPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

/** Returns an index i with a[i] == x, or -1 when x is not in a. The list must be sorted. */
fun <T : Comparable<T>> binarySearch(a: List<T>, x: T): Int {
    var lo = 0 // @line L1
    var hi = a.size
    while (lo < hi) { // @line L2
        val mid = lo + (hi - lo) / 2 // @line L3
        val c = a[mid].compareTo(x)
        if (c < 0) { // @line L4
            lo = mid + 1 // @line L5
        } else if (c > 0) { // @line L6
            hi = mid // @line L7
        } else {
            return mid // @line L8
        }
    }
    return -1 // @line L9
}

BinarySearchTest.kt 37 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.

import kotlin.random.Random
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

class BinarySearchTest {
    @Test
    fun examples() {
        val a = listOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
        assertEquals(5, binarySearch(a, 23))
        assertEquals(0, binarySearch(a, 2))
        assertEquals(9, binarySearch(a, 91))
        assertEquals(-1, binarySearch(a, 30))
        assertEquals(-1, binarySearch(a, 1))
        assertEquals(-1, binarySearch(a, 100))
    }

    @Test
    fun edges() {
        assertEquals(-1, binarySearch(emptyList<Int>(), 1))
        assertEquals(0, binarySearch(listOf(7), 7))
        assertEquals(1, binarySearch(listOf("ant", "bee", "cat"), "bee"))
    }

    @Test
    fun randomAgainstLinearScan() {
        val rng = Random(2150)
        repeat(2000) {
            val a = List(rng.nextInt(31)) { rng.nextInt(41) - 20 }.sorted()
            val x = rng.nextInt(51) - 25
            val got = binarySearch(a, x)
            if (x in a) assertEquals(x, a[got]) else assertEquals(-1, got)
        }
    }
}

History

John Mauchly described binary search in the Moore School Lectures in 1946. The first published version that works for each $n$ , not only for $n = 2^k - 1$ , is by Derrick Henry Lehmer in 1960. Knuth says that the idea is simple, but the details are hard. Jon Bentley found that most professional programmers in his courses wrote a binary search with a bug. In 2006 Joshua Bloch showed the overflow bug of the midpoint in the Java library.

References

Donald E. Knuth, The Art of Computer Programming, Volume 3, second edition, Section 6.2.1, Algorithm B
Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Exercise 2.3-6
Joshua Bloch, Nearly all binary searches and mergesorts are broken (2006). the overflow of (lo + hi) / 2

Ladder	Level	What the next level needs
Human proof		a full proof of time.average a full proof of time.best a full proof of time.worst a full proof of space.extra
Lean		name a Lean module in the lean field (07)
Code (c)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (cpp)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (csharp)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (go)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (java)		the native tests fail I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (javascript)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (kotlin)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (python)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (rust)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (typescript)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Visual		V2 needs the oracle check V03, line-trace agreement V06, the counter check V07 and the budgets V08 (10.8.2)
Writing		the lead paragraph