Binary search and its ordered-search relatives: interpolation, Fibonacci, rotated-array, matrix, parametric, and offline variants.
| index | slug | name |
|---|---|---|
| 21 | binary-search | Binary Search |
| 22 | iterative-binary-search | Iterative Binary Search |
| 23 | recursive-binary-search | Recursive Binary Search |
| 24 | lower-bound | Lower Bound |
| 25 | upper-bound | Upper Bound |
| 26 | equal-range-search | Equal Range Search |
| 27 | first-true-binary-search | First True Binary Search |
| 28 | last-true-binary-search | Last True Binary Search |
| 29 | binary-search-on-answer | Binary Search on Answer |
| 30 | exponential-search | Exponential Search |
| 31 | galloping-search | Galloping Search |
| 32 | interpolation-search | Interpolation Search |
| 33 | uniform-binary-search | Uniform Binary Search |
| 34 | fibonacci-search | Fibonacci Search |
| 35 | jump-search | Jump Search |
| 36 | ternary-search-discrete | Discrete Ternary Search |
| 37 | ternary-search-continuous | Continuous Ternary Search |
| 38 | rotated-array-search | Rotated Array Search |
| 39 | rotated-array-minimum-search | Rotated Array Minimum Search |
| 40 | bitonic-array-search | Bitonic Array Search |
| 41 | peak-finding-one-dimensional | One Dimensional Peak Finding |
| 42 | peak-finding-two-dimensional | Two Dimensional Peak Finding |
| 43 | matrix-binary-search | Matrix Binary Search |
| 44 | saddleback-search | Saddleback Search |
| 45 | sorted-matrix-search | Sorted Matrix Search |
| 46 | fractional-cascading-search | Fractional Cascading Search |
| 47 | binary-lifting-search | Binary Lifting Search |
| 48 | powers-of-two-search | Powers of Two Search |
| 49 | parametric-search | Parametric Search |
| 50 | parallel-binary-search | Parallel Binary Search |
| 51 | offline-binary-search | Offline Binary Search |
| 52 | parallel-binary-search-dsu | Parallel Binary Search with DSU |
| 53 | continuous-bisection-method | Bisection Method |
| 54 | monotone-predicate-search | Monotone Predicate Search |
| 55 | integer-square-root-binary-search | Integer Square Root by Binary Search |
Binary SearchSearch a sorted array by repeatedly halving the search interval.
Iterative Binary SearchBinary search implemented using a loop without recursion.
Recursive Binary SearchBinary search implemented using recursion over a shrinking interval.
Lower BoundFind the first position where a value can be inserted without violating sorted order.
Upper BoundFind the first index where elements become strictly greater than a given value.
Equal RangeFind the range of indices containing all occurrences of a value in a sorted array.
First True Binary SearchFind the first position where a monotone predicate becomes true.
Last True Binary SearchFind the last position where a monotone predicate remains true.
Binary Search on AnswerFind an optimal value by binary searching a monotone feasibility condition.
Exponential SearchLocate a search interval by exponential growth, then apply binary search.
Galloping SearchExpand the search range exponentially from a starting position, then apply binary search.
Interpolation SearchSearch a sorted numeric array by estimating the likely position of the target from its value.
Uniform Binary SearchBinary search variant that uses precomputed step sizes instead of dynamic midpoint calculation.
Fibonacci SearchSearch a sorted array using Fibonacci numbers to divide the range.
Jump SearchSearch a sorted array by jumping in fixed steps, then performing a linear scan within a block.
Discrete Ternary SearchFind the maximum or minimum of a unimodal function defined on discrete indices.
Continuous Ternary SearchFind the maximum or minimum of a unimodal function over a continuous domain.
Rotated Array SearchSearch a value in a sorted array that has been rotated around an unknown pivot.
Rotated Array Minimum SearchFind the smallest element in a sorted array that has been rotated around an unknown pivot.
Bitonic Array SearchSearch a value in an array that first increases and then decreases.
One Dimensional Peak FindingFind an element that is at least as large as its immediate neighbors.
Two Dimensional Peak FindingFind a peak element in a 2D grid using divide and conquer.
Matrix Binary SearchSearch a row-major sorted matrix by treating it as a virtual sorted array.
Saddleback SearchSearch a matrix sorted by rows and columns using a monotone path from a corner.
Sorted Matrix SearchSearch a matrix sorted by rows and columns using divide and conquer.
Fractional Cascading SearchSpeed up repeated binary searches across related sorted lists by linking sampled elements between lists.
Binary Lifting SearchFind a target state by jumping through powers of two in a precomputed lifting table.
Powers of Two SearchSearch for a boundary by trying decreasing jumps whose lengths are powers of two.
Parametric SearchConvert an optimization problem into a decision problem and search the parameter space.
Parallel Binary SearchAnswer many offline queries by searching their answers simultaneously with shared checks.
Offline Binary SearchAnswer many monotone queries by processing them together after all input is known.
Parallel Binary Search with DSUAnswer offline connectivity queries by combining parallel binary search with a disjoint set union.
Bisection MethodFind a root of a continuous function by repeatedly halving an interval where the function changes sign.
Monotone Predicate SearchFind the boundary where a Boolean predicate changes value over an ordered domain.
Integer Square RootCompute the floor of the square root of a nonnegative integer using binary search.