Like binary search, but the window is cut at Fibonacci sizes instead of in half: a window of F(k) − 1 positions splits around one probe into windows of F(k − 2) − 1 and F(k − 1) − 1. Moving to the next window needs only subtraction.
- Average time
- O(log n)
- Space
- O(1)