Binary Search Theory

Binary Search repeatedly halves the search interval on sorted or monotonic domains. Its tight logarithmic complexity underpins numerous higher-level algorithms and optimization strategies.

Divide / Conquer / Combine

Divide: Choose midpoint mid of [lo, hi].
Conquer: Recurse (or iterate) into half containing target.
Combine: No work; propagate found index or -1.

Recurrence & Correctness

Recurrence: T(n) = T(n/2) + O(1) → O(log n).

Invariant: Target (if present) always lies within [lo, hi].

Termination: Interval shrinks until found or lo > hi.

Comparisons: ⌊log2 n⌋ + O(1) worst.

Overflow safe mid: lo + ((hi - lo) >> 1).

Answer-space use: Search monotonic predicates (e.g., feasibility tests).

Recursive Pseudocode

Pseudocode

1function binarySearch(arr, target):
2  lo = 0; hi = length(arr) - 1
3  while lo <= hi:
4    mid = (lo + hi) // 2
5    if arr[mid] == target: return mid
6    if arr[mid] < target: lo = mid + 1 else hi = mid - 1
7  return -1

Iterative Implementations

Python

Pseudocode

Python

1def binary_search(arr, target):
2    lo, hi = 0, len(arr) - 1
3    while lo <= hi:
4        mid = (lo + hi) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            lo = mid + 1
9        else:
10            hi = mid - 1
11    return -1

TypeScript

Pseudocode

TypeScript

1export function binarySearch(arr: number[], target: number): number {
2  let lo = 0, hi = arr.length - 1;
3  while (lo <= hi) {
4    const mid = (lo + hi) >> 1;
5    if (arr[mid] === target) return mid;
6    if (arr[mid] < target) lo = mid + 1; else hi = mid - 1;
7  }
8  return -1;
9}

Edge Cases & Variants

Empty array → -1.
Out-of-range target prunes quickly.
Duplicates: use lower/upper bound modifications.
Floating / continuous domains: guard infinite loops with epsilon.

Binary search on answer (optimize monotonic metric).
First true predicate (boolean monotonic sequence).
Ternary search (unimodal functions).
Exponential + binary (unknown length / unbounded range).

Applications & Use Cases

Applications

Lookup tables
Boundary finding
Optimization search

Use Cases

Lower/upper bounds
Square root / monotonic predicate
Parametric search

Advantages

Fast on large sorted data
Simple iterative form
Low memory

Quick Sort Go to Simulation Maximum Subarray (D&C)

Recurrence & Correctness

Recurrence: T(n) = T(n/2) + O(1) → O(log n).

Invariant: Target (if present) always lies within [lo, hi].

Termination: Interval shrinks until found or lo > hi.

Comparisons: ⌊log2 n⌋ + O(1) worst.

Overflow safe mid: lo + ((hi - lo) >> 1).

Answer-space use: Search monotonic predicates (e.g., feasibility tests).

1function binarySearch(arr, target): 2 lo = 0; hi = length(arr) - 1 3 while lo <= hi: 4 mid = (lo + hi) // 2 5 if arr[mid] == target: return mid 6 if arr[mid] < target: lo = mid + 1 else hi = mid - 1 7 return -1

Iterative Implementations

Python

Pseudocode

Python

1def binary_search(arr, target):
2    lo, hi = 0, len(arr) - 1
3    while lo <= hi:
4        mid = (lo + hi) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            lo = mid + 1
9        else:
10            hi = mid - 1
11    return -1

TypeScript

Pseudocode

TypeScript

1export function binarySearch(arr: number[], target: number): number {
2  let lo = 0, hi = arr.length - 1;
3  while (lo <= hi) {
4    const mid = (lo + hi) >> 1;
5    if (arr[mid] === target) return mid;
6    if (arr[mid] < target) lo = mid + 1; else hi = mid - 1;
7  }
8  return -1;
9}

Edge Cases & Variants

Empty array → -1.
Out-of-range target prunes quickly.
Duplicates: use lower/upper bound modifications.
Floating / continuous domains: guard infinite loops with epsilon.

Binary search on answer (optimize monotonic metric).
First true predicate (boolean monotonic sequence).
Ternary search (unimodal functions).
Exponential + binary (unknown length / unbounded range).