2. Binary Search and Ordered Search

Binary search and its ordered-search relatives: interpolation, Fibonacci, rotated-array, matrix, parametric, and offline variants.

35 items

2. Binary search and ordered search, 35

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
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Binary Search

Search a sorted array by repeatedly halving the search interval.
algorithms searching binary-search arrays
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Iterative Binary Search

Binary search implemented using a loop without recursion.
algorithms searching binary-search iterative
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Recursive Binary Search

Binary search implemented using recursion over a shrinking interval.
algorithms searching binary-search recursion
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Lower Bound

Find the first position where a value can be inserted without violating sorted order.
algorithms searching binary-search lower-bound
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Upper Bound

Find the first index where elements become strictly greater than a given value.
algorithms searching binary-search upper-bound
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Equal Range

Find the range of indices containing all occurrences of a value in a sorted array.
algorithms searching binary-search range-query
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

First True Binary Search

Find the first position where a monotone predicate becomes true.
algorithms searching binary-search monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Last True Binary Search

Find the last position where a monotone predicate remains true.
algorithms searching binary-search monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Binary Search on Answer

Find an optimal value by binary searching a monotone feasibility condition.
algorithms searching binary-search optimization monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Exponential Search

Locate a search interval by exponential growth, then apply binary search.
algorithms searching exponential-search binary-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Galloping Search

Expand the search range exponentially from a starting position, then apply binary search.
algorithms searching galloping-search exponential-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Interpolation Search

Search a sorted numeric array by estimating the likely position of the target from its value.
algorithms searching interpolation-search ordered-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Uniform Binary Search

Binary search variant that uses precomputed step sizes instead of dynamic midpoint calculation.
algorithms searching binary-search uniform-binary-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Fibonacci Search

Search a sorted array using Fibonacci numbers to divide the range.
algorithms searching fibonacci-search ordered-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Jump Search

Search a sorted array by jumping in fixed steps, then performing a linear scan within a block.
algorithms searching jump-search ordered-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Discrete Ternary Search

Find the maximum or minimum of a unimodal function defined on discrete indices.
algorithms searching ternary-search optimization
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Continuous Ternary Search

Find the maximum or minimum of a unimodal function over a continuous domain.
algorithms searching ternary-search optimization continuous
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Rotated Array Search

Search a value in a sorted array that has been rotated around an unknown pivot.
algorithms searching binary-search rotated-array
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Rotated Array Minimum Search

Find the smallest element in a sorted array that has been rotated around an unknown pivot.
algorithms searching binary-search rotated-array
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Bitonic Array Search

Search a value in an array that first increases and then decreases.
algorithms searching bitonic-array binary-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

One Dimensional Peak Finding

Find an element that is at least as large as its immediate neighbors.
algorithms searching peak-finding binary-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Two Dimensional Peak Finding

Find a peak element in a 2D grid using divide and conquer.
algorithms searching peak-finding divide-and-conquer
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Matrix Binary Search

Search a row-major sorted matrix by treating it as a virtual sorted array.
algorithms searching binary-search matrix
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Saddleback Search

Search a matrix sorted by rows and columns using a monotone path from a corner.
algorithms searching matrix saddleback-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Sorted Matrix Search

Search a matrix sorted by rows and columns using divide and conquer.
algorithms searching matrix divide-and-conquer
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Fractional Cascading Search

Speed up repeated binary searches across related sorted lists by linking sampled elements between lists.
algorithms searching binary-search data-structures
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Binary Lifting Search

Find a target state by jumping through powers of two in a precomputed lifting table.
algorithms searching binary-lifting tree-algorithms
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Powers of Two Search

Search for a boundary by trying decreasing jumps whose lengths are powers of two.
algorithms searching binary-search monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Parametric Search

Convert an optimization problem into a decision problem and search the parameter space.
algorithms searching parametric-search optimization decision-problem
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Parallel Binary Search

Answer many offline queries by searching their answers simultaneously with shared checks.
algorithms searching binary-search offline-queries
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Offline Binary Search

Answer many monotone queries by processing them together after all input is known.
algorithms searching binary-search offline-algorithms
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Parallel Binary Search with DSU

Answer offline connectivity queries by combining parallel binary search with a disjoint set union.
algorithms searching binary-search dsu offline-queries
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Bisection Method

Find a root of a continuous function by repeatedly halving an interval where the function changes sign.
algorithms searching binary-search numerical-methods root-finding
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Monotone Predicate Search

Find the boundary where a Boolean predicate changes value over an ordered domain.
algorithms searching binary-search monotone-predicate
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Integer Square Root

Compute the floor of the square root of a nonnegative integer using binary search.
algorithms searching binary-search integer-arithmetic