Derek Lawless

There is always sunshine. Far above the grey sky

Binary Search

| 2 min read

A binary search employs a divide and conquer strategy to find the position of a target value in a sorted list. A binary search is also known as a half-interval search, logarithmic search, or binary chop.

For binary search to work the list must be sorted (sorting is a discussion for another time).

Given a sorted list from which we want to find the number 35:

Binary search

Begin by splitting the list into two halves, disregarding the half that is less than, or greater than, 35:

Binary search

Split the remaining half into two — again disregarding the half that is less than, or greater than, 35:

Binary search

Repeating again finds 35 at position 5 in the list:

Binary search

Complexity

🔔 Complexity is considered in terms of worst case.

Time

Notes
Θ(log n)

Space

Notes
Θ(1) Requires three pointers to the list elements, regardless of list size

An implementation

// TypeScript
export interface IBinarySearchResult {
	position: number;
}

export function binarySearch<T>(values: T[] = [], target: T): IBinarySearchResult {
	let low = 0;
	let high = values.length - 1;

	while (low <= high) {
		const middle = Math.floor((low + high) / 2);
		if (values[middle] === target) {
			return {
				position: middle,
			};
		}
		if (target < values[middle]) {
			high = middle - 1;
		} else {
			low = middle + 1;
		}
	}

	return {
		position: -1,
	};
}

A recursive alternative

// TypeScript
export function binarySearchRecursive<T>(
	values: T[] = [],
	target: T,
	low: number = 0,
	high: number = values.length - 1): IBinarySearchResult {

	if (low <= high) {
		const middle = Math.floor((low + high) / 2);
		if (values[middle] === target) {
			return {
				position: middle,
			};
		} else if (target < values[middle]) {
			return binarySearchRecursive(values, target, low, middle - 1);
		} else {
			return binarySearchRecursive(values, target, middle + 1, high);
		}
	}

	return {
		position: -1,
	};
}

Code on Github

© 2020 Derek Lawless. Built with Gatsby