Binary Search
Algorithms and Data Structures
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.
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,
};
}