Exponential search

O(log n)

Exponential search najde rozsah obsahující hledanou hodnotu zdvojnásobováním indexu (1, 2, 4, 8, …), dokud hodnota nepřekročí hledanou, a pak v tom rozsahu spustí binární vyhledávání. Hodí se pro neohraničené nebo velmi velké seřazené vstupy, kde předem neznáš velikost. O(log n).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Zkontroluj index 0, pak index zdvojnásobuj (1, 2, 4, …), dokud jeho hodnota nepřekročí hledanou.
  2. To dá rozsah [bound/2, bound], který musí hledanou hodnotu obsahovat, pokud tam je.
  3. Binárně prohledej ten rozsah.
  4. Když najdeš, ohlas index; jinak že hodnota chybí.

Pseudokód

1exponentialSearch(a, target):       # O(log n) — a is sorted2  if a[0] = target: return 03  bound ← 14  while bound < n and a[bound] ≤ target:5    bound ← bound * 26  binarySearch(a, target, bound/2, min(bound, n-1))