fibonaccihakumenetelmä

The fibonacci hakumenetelmä, commonly known as the Fibonacci search method, is a search algorithm used to locate a target value within a sorted array or list. It uses Fibonacci numbers to determine probe positions and repeatedly narrows the search interval until the key is found or the interval is exhausted.

In practice, the method starts by finding a Fibonacci number that is at least as large as the size of the array. An offset is maintained to mark the eliminated portion. At each step, the probe index is chosen as offset plus a smaller Fibonacci number, ensuring the remaining search space is a consecutive block whose size is a Fibonacci number. The value at the probe index is compared with the target. If it is smaller, the offset is moved forward and the Fibonacci numbers are updated to reflect the new, smaller range. If it is larger, the upper portion is discarded and the numbers are adjusted accordingly. If it is equal, the index is returned. When the remaining Fibonacci number becomes 1, a final check may be performed at offset+1.

Performance-wise, the Fibonacci search has a worst-case time complexity of O(log n), similar to binary search, but with a different constant factor for the number of comparisons. It uses only additions, subtractions, and comparisons, and typically does not require division. While binary search is frequently preferred on modern hardware, Fibonacci search can be advantageous in contexts where the cost of data access patterns or division is a concern.

Related algorithms include binary search and interpolation search. The method is a classical approach in the family of search techniques that partition the search space using Fibonacci numbers.