Fibonacci search technique

In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search, Fibonacci search examines locations whose addresses have lower dispersion. Therefore, when the elements being searched have non-uniform access memory storage (i.e., the time needed to access a storage location varies depending on the location previously accessed), the Fibonacci search has an advantage over binary search in slightly reducing the average time needed to access a storage location. Note, however, that large arrays not fitting in CPU cache or even in RAM can also be considered as non-uniform access examples. Fibonacci search has a complexity of O(log(n)) (see Big O notation).