Binary search and variants
typescriptA comprehensive collection of generic binary search variants in TypeScript, including classic binary search, lower bound, upper bound, and search range functions with support for custom comparators.
Code
type Comparator<T> = (a: T, b: T) => number;
const defaultComparator = <T>(a: T, b: T): number => {
if (a < b) return -1;
if (a > b) return 1;
return 0;
};
/**
* Classic binary search - finds the index of target in a sorted array
* @returns index of target, or -1 if not found
*/
export function binarySearch<T>(
arr: readonly T[],
target: T,
comparator: Comparator<T> = defaultComparator
): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
const cmp = comparator(arr[mid], target);
if (cmp === 0) {
return mid;
} else if (cmp < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
/**
* Lower bound - finds the first index where arr[index] >= target
* @returns index of first element >= target, or arr.length if all elements are smaller
*/
export function lowerBound<T>(
arr: readonly T[],
target: T,
comparator: Comparator<T> = defaultComparator
): number {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
const cmp = comparator(arr[mid], target);
if (cmp < 0) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
/**
* Upper bound - finds the first index where arr[index] > target
* @returns index of first element > target, or arr.length if all elements are <= target
*/
export function upperBound<T>(
arr: readonly T[],
target: T,
comparator: Comparator<T> = defaultComparator
): number {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
const cmp = comparator(arr[mid], target);
if (cmp <= 0) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
/**
* Search range - finds the starting and ending position of target in sorted array
* @returns [startIndex, endIndex] or [-1, -1] if target is not found
*/
export function searchRange<T>(
arr: readonly T[],
target: T,
comparator: Comparator<T> = defaultComparator
): [number, number] {
const lower = lowerBound(arr, target, comparator);
if (lower === arr.length || comparator(arr[lower], target) !== 0) {
return [-1, -1];
}
const upper = upperBound(arr, target, comparator);
return [lower, upper - 1];
}
// Example usage with numbers
const numbers = [1, 2, 3, 3, 3, 4, 5, 6];
console.log('Array:', numbers);
console.log('binarySearch(3):', binarySearch(numbers, 3));
console.log('lowerBound(3):', lowerBound(numbers, 3));
console.log('upperBound(3):', upperBound(numbers, 3));
console.log('searchRange(3):', searchRange(numbers, 3));
console.log('searchRange(7):', searchRange(numbers, 7));
// Example with custom objects and comparator
interface Product {
id: number;
name: string;
price: number;
}
const products: Product[] = [
{ id: 1, name: 'Apple', price: 1.5 },
{ id: 2, name: 'Banana', price: 2.0 },
{ id: 3, name: 'Cherry', price: 3.0 },
{ id: 4, name: 'Date', price: 3.0 },
{ id: 5, name: 'Elderberry', price: 5.0 },
];
const priceComparator: Comparator<Product> = (a, b) => a.price - b.price;
const targetProduct: Product = { id: 0, name: '', price: 3.0 };
console.log('\nProducts by price:');
console.log('lowerBound(price: 3.0):', lowerBound(products, targetProduct, priceComparator));
console.log('upperBound(price: 3.0):', upperBound(products, targetProduct, priceComparator));
console.log('searchRange(price: 3.0):', searchRange(products, targetProduct, priceComparator));How It Works
This implementation provides four essential binary search variants that cover the most common search scenarios in sorted arrays. The classic binarySearch function returns the exact index of a target element or -1 if not found. The lowerBound function finds the insertion point where an element would go to maintain sorted order (first position where element >= target), while upperBound finds the position just after all matching elements (first position where element > target). The searchRange function combines these to efficiently find all occurrences of a value.
The key design decision here is using generics with a custom comparator pattern, similar to C++ STL. This allows the functions to work with any data type—primitives, objects, or complex nested structures. The default comparator handles basic comparable types using JavaScript's native comparison operators. For objects, you provide a comparator that extracts and compares the relevant property, as shown in the Product example where we search by price.
A critical implementation detail is the calculation of the middle index using left + Math.floor((right - left) / 2) instead of Math.floor((left + right) / 2). While JavaScript numbers can handle large values, this pattern prevents potential overflow issues in other languages and is considered best practice. Additionally, using readonly T[] for the array type signals that these functions don't modify the input and allows passing both mutable and immutable arrays.
The boundary conditions differ between variants: classic binary search uses left <= right with right = arr.length - 1, while lower/upper bound use left < right with right = arr.length. This distinction is intentional—the bound functions need to potentially return an index equal to the array length to indicate "all elements are smaller/smaller-or-equal." Understanding these boundary conditions is crucial for correctly implementing binary search variants.
Use these functions when you have sorted data and need O(log n) search performance. They're particularly valuable for finding ranges of duplicate values, determining insertion points, or implementing features like autocomplete suggestions. Avoid them if your data isn't sorted (sort first or use a hash-based structure) or if the array is very small (linear search has less overhead for tiny arrays).