Binary search

Binary search locates a target in an ordered collection by repeatedly eliminating half of the remaining search interval. It can also determine that the target is absent.

Search interval: A contiguous range of candidate positions that an algorithm examines for a target. Binary search maintains this range and narrows it after each comparison.
Sorted array: An array whose elements are arranged in a specified order. Binary search relies on sorted order to rule out an entire half after a comparison.
Binary search tree: A tree structure whose keys are ordered so each node separates smaller keys from larger ones. It uses comparisons to guide a search, but stores the ordered structure as linked nodes rather than an array.
Linear search: A search algorithm that checks elements one by one until it finds a target or reaches the end. It works without sorted data, but may inspect every element.
Loop invariant: A condition that remains true before and after every iteration of a loop. The target, if present, must remain within the interval at every iteration.
Comparison function: A function that determines the ordering relation between two values. Each step needs a consistent comparison between the target and the midpoint value.
Bisection method: A numerical method that finds a root by repeatedly halving an interval with opposite-sign endpoint values. It applies the same interval-halving logic to locate a zero of a function.
Hash table: A data structure that maps keys to positions using a hash function. It supports fast exact-key lookup without requiring sorted order, unlike binary search.
Off-by-one error: A boundary mistake caused by counting one position too many or too few. Incorrect interval endpoints can skip candidates or prevent termination.
Divide-and-conquer algorithm: An algorithmic strategy that breaks a problem into smaller subproblems and combines their results. Binary search is a particularly simple divide-and-conquer algorithm that keeps only one subproblem.

Linked from 13 pages