Binary Search in Python, Java and TypeScript

An exact search and a lower bound in each language, then the built-in that does each.

Binary search comes in two shapes worth writing by hand: an exact search over a closed range that returns the index of the target or -1, and a lower bound over a half-open range that returns the first index whose value is at least the target. This card gives both in Python, Java and TypeScript, run on 4 9 15 21 28 37 44 52, and then the function each standard library already provides. Each listing searches for 44, which is present, and 30, which is not. The highlighted lines are the two loop conditions and the line that sets high in the lower bound.

An exact search and a lower bound on eight sorted numbers, in each language

binary_search_code.pypy

from bisect import bisect_left, bisect_right


def binary_search(items: list[int], target: int) -> int:
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1


def lower_bound(items: list[int], target: int) -> int:
    low, high = 0, len(items)
    while low < high:
        mid = (low + high) // 2
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low


numbers = [4, 9, 15, 21, 28, 37, 44, 52]
print("search 44:", binary_search(numbers, 44))
print("search 30:", binary_search(numbers, 30))
print("lower bound 30:", lower_bound(numbers, 30))
print("lower bound 44:", lower_bound(numbers, 44))
print("bisect_left 30:", bisect_left(numbers, 30))
print("bisect_right 44:", bisect_right(numbers, 44))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

search 44: 6
search 30: -1
lower bound 30: 5
lower bound 44: 6
bisect_left 30: 5
bisect_right 44: 7

BinarySearchCode.javajava

import java.util.Arrays;

public class BinarySearchCode {
    static int binarySearch(int[] items, int target) {
        int low = 0;
        int high = items.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (items[mid] == target) {
                return mid;
            }
            if (items[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    static int lowerBound(int[] items, int target) {
        int low = 0;
        int high = items.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (items[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] numbers = {4, 9, 15, 21, 28, 37, 44, 52};
        System.out.println("search 44: " + binarySearch(numbers, 44));
        System.out.println("search 30: " + binarySearch(numbers, 30));
        System.out.println("lower bound 30: " + lowerBound(numbers, 30));
        System.out.println("lower bound 44: " + lowerBound(numbers, 44));
        System.out.println("Arrays.binarySearch 44: " + Arrays.binarySearch(numbers, 44));
        System.out.println("Arrays.binarySearch 30: " + Arrays.binarySearch(numbers, 30));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

search 44: 6
search 30: -1
lower bound 30: 5
lower bound 44: 6
Arrays.binarySearch 44: 6
Arrays.binarySearch 30: -6

binary_search_code.tsts

function binarySearch(items: number[], target: number): number {
  let low = 0;
  let high = items.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (items[mid] === target) {
      return mid;
    }
    if (items[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

function lowerBound(items: number[], target: number): number {
  let low = 0;
  let high = items.length;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (items[mid] < target) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  return low;
}

const numbers: number[] = [4, 9, 15, 21, 28, 37, 44, 52];
console.log(`search 44: ${binarySearch(numbers, 44)}`);
console.log(`search 30: ${binarySearch(numbers, 30)}`);
console.log(`lower bound 30: ${lowerBound(numbers, 30)}`);
console.log(`lower bound 44: ${lowerBound(numbers, 44)}`);

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

search 44: 6
search 30: -1
lower bound 30: 5
lower bound 44: 6

All three hand-written versions printed the same four lines: 44 found at index 6, 30 missing, and lower bounds of 5 and 6. The exact search loops while low <= high, because a one-item range still has to be checked. The lower bound loops while low < high and sets high = mid, because high is one past the range and the middle value may be the answer. The midpoint differs by language: Python's // rounds down and its integers cannot overflow, Java uses low + (high - low) / 2 so the sum never passes the largest int, and TypeScript needs Math.floor because / returns a fraction.

Python's bisect module is the built-in for bounds. bisect_left is the lower bound and bisect_right the upper bound: it printed 7 for 44, one past the single 44. Since Python 3.10 both accept a key function. Java's Arrays.binarySearch, with Collections.binarySearch for a list, is an exact search: it printed 6 for 44 and -6 for 30, a negative number that encodes where 30 would go. With repeated values its documentation promises no particular one of them. TypeScript has no built-in binary search; indexOf and includes on an array scan from the front in O(n), so the hand-written functions above are the usual answer.

← → move through sections and cards