ConceptDBISAI-written · not yet proofread

Exponential Search

Also Galloping Search

Exponential (galloping) search locates a value x in a sorted array by probing positions with exponentially growing distance (1, 3, 7, …, 2^i − 1) until an element ≥ x is found and then binary searching the last interval, in O(log d) time for d the position of x.

Formula#

For $x$ at position $d$ in $A$ :

\text{time} = \underbrace{O(\log d)}_{\text{doubling phase}} + \underbrace{O(\log d)}_{\text{binary search in an interval of length} < d} = O(\log d)

Properties#

Proof

Let $j_1, \ldots, j_k$ be the probed positions, $j_i = 2^i - 1$ .
The search did not stop at $j_{k-1}$ , so $j_{k-1} < d$ , i.e. $2^{k-1} - 1 < d$ , hence $2^{k-1} \leq d$ and $k \leq \log_2 d + 1$ . The doubling phase takes $O(k) = O(\log d)$ steps.
Hence $j_k = 2^k - 1 \leq 2^{\log_2 d + 1} - 1 < 2d$ . The binary search halves its interval (of length $< 2d$ ) in every step, so it takes $O(\log(2d)) = O(\log 2 + \log d) = O(\log d)$ steps.
Both phases together: $O(\log d)$ . $\blacksquare$

Proof

After $k$ jumps the probed position is $0 + 1 + 2 + \ldots + 2^{k-1} = 2^k - 1$ . The search stops there, so $2^k - 1 \geq i$ , i.e. $k \geq \log_2(i+1)$ .
It did not stop one jump earlier, at position $2^{k-1} - 1$ , so $2^{k-1} - 1 < i$ , i.e. $k - 1 < \log_2(i+1)$ .
Hence $k$ is the smallest integer $\geq \log_2(i+1)$ : $k = \lceil \log_2(i+1) \rceil$ . $\blacksquare$

Doubling variant. DBIS Exam WS2223 (not published) (Task 1.1) probes the positions $0, 1, 2, 4, 8, \dots$ (i = max(2 * i, 1)) instead. For $j$ the smallest index with $A[j] = x$ this returns an index $i$ with $j \leq i \leq 2j$ in $O(\log(1 + j))$ time; the $1 +$ handles $j = 0$ .
Use in list intersection. Searching each element of the shorter list in the longer one with galloping search, each search starting where the previous one stopped, gives the $O(k \cdot \log(1 + n/k))$ intersection algorithm (List Intersection > 3. Galloping (Exponential) Search Intersection).
Compared with plain binary search over the whole array ( $O(\log n)$ ), the cost depends only on the distance $d$ to the target, not on the array length $n$ ; this pays off when the target is near the start.

Example#

$A = [2, 3, 5, 8, 13, 21, 34, 55, 89, 144]$ , $x = 34$ (position $d = 6$ ):

Doubling phase: probe $A[0] = 2$ , $A[1] = 3$ , $A[3] = 8$ (all $< 34$ ), then $A[7] = 55 \geq 34$ : stop after $k = 3$ jumps ( $\lceil \log_2(7 + 1) \rceil = 3$ with $i = 7$ the first position with $A[i] > 34$ ).
Binary search in positions $4..7$ : $A[5] = 21 < 34$ , then $A[6] = 34$ : found.

Sources#

DBIS Exam WS1920 (not published) Task 1.3 (number of jumps), DBIS Exam WS2122 (not published) Task 1.4 ( $O(\log d)$ proof), DBIS Exam WS2223 (not published) Task 1.1 (implementation)
DBIS Exam WS1819 (not published) Task 1.2 (galloping search intersection)
Not lectured in WS 25/26; DBIS_VL01 > Query Processing covers only the linear-time zipper.

Connections

Mentioned in inline links2

List Intersection
A refinement of binary search: for each element $x$ of the shorter list, run an exponential (galloping) search in the longer list: find a range $[2^{j-1}, 2^j]$ in which $x$ could lie by doubling the index, then binary search within that r… §
List Intersection and Search
Exponential Search — galloping search for one value in a sorted array in $O(\log d)$ ; the building block of the fastest intersection §
| Galloping search intersection | $O(k \log(1 + n/k))$ | Exponential Search from the previous position, then binary search | §

Search in these mentions →