#fibonacci-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...