tag

#exponential-search

2 pages tagged

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

Exponential Search

Exponential Search Exponential search finds a target in a sorted array by first locating a range where the target may lie, then applying binary search within that range. It is effective when the position of the target is near the beginning or when the array size is unknown. Problem Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that $$ A[i] =...

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

Galloping Search

Galloping Search Galloping search extends exponential search by starting from a known position instead of the beginning of the array. It is designed for scenarios where you already have a nearby index and want to locate a target relative to that position. This technique appears in merge algorithms such as Timsort, where one run advances quickly into another. Problem Given a sorted array $A$, a starting index $s$, and a...