Fibonacci Search Algorithm

Fibonacci search locates a target value in a sorted array by dividing the array using Fibonacci numbers rather than the equal halves binary search uses, comparing the target against elements at positions determined by successive Fibonacci numbers and narrowing the search range accordingly at each step until the target is found or the range is empty. Because it only requires addition and subtraction to compute its comparison points rather than division, it was historically useful on hardware where division was slow relative to addition. It runs in O(log n) time, the same asymptotic bound as binary search, and traces to Jack Kiefer's related 1950s work on Fibonacci search for optimizing unimodal functions, later adapted to array searching.