# Derek Lawless

There is always sunshine. Far above the grey sky

# Binary Search

## 21st November 2020 | 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`: Begin by splitting the list into two halves, disregarding the half that is less than, or greater than, `35`: Split the remaining half into two — again disregarding the half that is less than, or greater than, `35`: Repeating again finds `35` at position `5` in the list: ## Complexity

🔔 Complexity is considered in terms of worst case.

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