tag

#ordered-search

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Fibonacci Search

Fibonacci Search Fibonacci search is a variant of binary search that uses Fibonacci numbers to divide the search interval. Instead of halving the range, it splits according to Fibonacci offsets. It avoids division and relies only on addition and subtraction, which made it useful on early hardware. Problem Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that $$ A[i] = x...
algorithms searching fibonacci-search ordered-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Interpolation Search

Interpolation Search Interpolation search is a search algorithm for sorted numeric arrays. Like binary search, it repeatedly narrows the search interval. Unlike binary search, it does not always choose the middle position. It estimates where the target should be based on the values at the ends of the interval. This works well when values are close to uniformly distributed. For example, if the target is near the value at the...
algorithms searching interpolation-search ordered-search
Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Jump Search

Jump Search Jump search finds a target in a sorted array by skipping ahead in fixed-size steps and then performing a linear scan within a small block. It reduces the number of comparisons compared to linear search while avoiding full binary search. Problem Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that $$ A[i] = x $$ If no such index...
algorithms searching jump-search ordered-search