Fibonacci search

O(log n)

Fibonacci search je jako binární vyhledávání, ale dělí rozsah v offsetech daných Fibonacciho čísly místo prostředku. Používá jen sčítání a odčítání (žádné dělení), což ho dělalo atraktivním na starém hardwaru, a sahá na pozice pole blízko u sebe (šetrné ke cache). Na seřazeném poli běží v O(log n).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Najdi nejmenší Fibonacciho číslo ≥ délka pole.
  2. Zkus pozici v offsetu daném menším Fibonacciho číslem.
  3. Když je hodnota menší, posuň Fibonacciho okno dolů a posuň offset.
  4. Když větší, zmenši okno dál; opakuj, dokud nenajdeš nebo nevyčerpáš.

Pseudokód

1fibonacciSearch(a, target):         # O(log n) — a is sorted2  grow Fibonacci numbers until fib ≥ n3  offset ← -14  while fib > 1:5    i ← min(offset + fib₋₂, n-1)6    if a[i] < target: shift fibs down; offset ← i7    else if a[i] > target: shift fibs down twice8    else: return i9  return (a[offset+1] = target) ? offset+1 : -1