Searching is one of the most common tasks in computer programming. Whether you’re finding a contact in your phone list, checking for a product in a database, or looking for a word in a dictionary, search algorithms make it possible to quickly locate what you need. Among the many search techniques available, one particularly elegant and efficient algorithm is Fibonacci Search.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is based on the Fibonacci sequence, a series of numbers where each number is the sum of the previous two. This search algorithm uses these numbers to divide the search range, similar to how Binary Search divides data in halves. The key difference is that Fibonacci Search does not necessarily check the middle element but instead uses Fibonacci numbers to determine where to split. This makes it useful in systems where accessing elements in memory is costly or uneven, such as databases or memory hierarchies.
In this article, we’ll explore different ways to implement Fibonacci Search in Python. Each section will walk you through a complete program — starting from the basic version and gradually moving towards more optimized and flexible implementations. By the end, you’ll not only understand the algorithm but also know how to adapt it for your own projects.
Program 1: Basic Iterative Fibonacci Search
This first program introduces the simplest way to implement Fibonacci Search using loops. It works efficiently for sorted arrays and uses iteration to find the desired element.
def fibonacci_search(arr, x):
n = len(arr)
fibMMm2 = 0
fibMMm1 = 1
fibM = fibMMm2 + fibMMm1
while fibM < n:
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
offset = -1
while fibM > 1:
i = min(offset + fibMMm2, n - 1)
if arr[i] < x:
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
elif arr[i] > x:
fibM = fibMMm2
fibMMm1 = fibMMm1 - fibMMm2
fibMMm2 = fibM - fibMMm1
else:
return i
if fibMMm1 and offset + 1 < n and arr[offset + 1] == x:
return offset + 1
return -1
arr = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90]
x = 85
index = fibonacci_search(arr, x)
if index != -1:
print(f"Element found at index {index}")
else:
print("Element not found")This code works by first generating Fibonacci numbers until one is greater than or equal to the array length. It then uses these numbers to determine which part of the array to explore next. In each step, the algorithm narrows down the range until it finds the target element or concludes that it’s not present. This iterative version is great for beginners because it clearly shows the logic flow.
Program 2: Recursive Fibonacci Search
In this version, we use recursion instead of loops. Recursion makes the logic more elegant and mathematical, allowing the function to call itself with new parameters until the element is found.
def fibonacci_search_recursive(arr, x, offset, fibMMm2, fibMMm1, fibM):
if fibM == 0:
return -1
i = min(offset + fibMMm2, len(arr) - 1)
if arr[i] == x:
return i
elif arr[i] < x:
# Move right
return fibonacci_search_recursive(arr, x, i, fibMMm1, fibM - fibMMm1, fibMMm1 + (fibM - fibMMm1))
else:
# Move left
return fibonacci_search_recursive(arr, x, offset, fibMMm2 - fibMMm1, fibMMm1, fibMMm2)
def start_search(arr, x):
n = len(arr)
fibMMm2 = 0
fibMMm1 = 1
fibM = fibMMm2 + fibMMm1
while fibM < n:
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
return fibonacci_search_recursive(arr, x, -1, fibMMm2, fibMMm1, fibM)
arr = [1, 3, 7, 15, 31, 63, 127]
x = 31
result = start_search(arr, x)
print(f"Element found at index {result}" if result != -1 else "Element not found")This version might look more complex, but it’s actually simpler in structure. The recursion replaces looping by repeatedly reducing the search range based on Fibonacci numbers. It’s a good way for learners to understand how recursion naturally fits into algorithms.
Program 3: Simplified Fibonacci Search for Small Arrays
Sometimes you don’t need the full complexity of the algorithm. This shorter version is great for experimenting with small arrays or when learning the basic concept of Fibonacci-based division.
def simple_fibonacci_search(arr, x):
n = len(arr)
fibMMm2, fibMMm1 = 0, 1
fibM = fibMMm2 + fibMMm1
while fibM < n:
fibMMm2, fibMMm1 = fibMMm1, fibM
fibM = fibMMm2 + fibMMm1
offset = -1
while fibM > 1:
i = min(offset + fibMMm2, n - 1)
if arr[i] < x:
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
elif arr[i] > x:
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
else:
return i
return -1
arr = [5, 10, 15, 20, 25]
x = 20
result = simple_fibonacci_search(arr, x)
print(f"Element found at index {result}" if result != -1 else "Element not found")This compact version is easy to read and understand. It uses the same logic as before but with fewer variables and shorter code, helping beginners quickly grasp how Fibonacci numbers guide the search process.
Program 4: Object-Oriented Fibonacci Search
For a more structured and reusable approach, we can write the Fibonacci Search algorithm as part of a class. This makes it easy to integrate into larger projects and promotes cleaner, modular code.
class FibonacciSearch:
def __init__(self, arr):
self.arr = arr
def search(self, x):
n = len(self.arr)
fibMMm2, fibMMm1 = 0, 1
fibM = fibMMm2 + fibMMm1
while fibM < n:
fibMMm2, fibMMm1 = fibMMm1, fibM
fibM = fibMMm2 + fibMMm1
offset = -1
while fibM > 1:
i = min(offset + fibMMm2, n - 1)
if self.arr[i] < x:
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
elif self.arr[i] > x:
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
else:
return i
return -1
arr = [2, 4, 6, 8, 10, 12, 14]
searcher = FibonacciSearch(arr)
x = 10
index = searcher.search(x)
print(f"Element found at index {index}" if index != -1 else "Element not found")This version encapsulates the logic inside a class, allowing you to easily create an instance and perform searches on different datasets. It’s a great step towards writing professional Python programs and understanding how algorithms can fit into object-oriented design.
Program 5: Fibonacci Search with Input Handling
Real-world programs should handle user inputs gracefully. This version adds input checking to prevent crashes and improves user interaction.
def fibonacci_search_safe(arr, x):
if not arr:
print("Array is empty.")
return -1
n = len(arr)
fibMMm2, fibMMm1 = 0, 1
fibM = fibMMm2 + fibMMm1
while fibM < n:
fibMMm2, fibMMm1 = fibMMm1, fibM
fibM = fibMMm2 + fibMMm1
offset = -1
while fibM > 1:
i = min(offset + fibMMm2, n - 1)
if arr[i] < x:
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
elif arr[i] > x:
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
else:
return i
return -1
arr = []
x = 50
result = fibonacci_search_safe(arr, x)
if result != -1:
print(f"Element found at index {result}")
else:
print("Element not found")This version checks for empty arrays and avoids runtime errors. It’s an excellent example of how to make your code safer and more user-friendly, which is crucial in professional programming.
Frequently Asked Questions (FAQ)
Here are some common questions that beginners often ask when learning Fibonacci Search.
Q1: What is Fibonacci Search used for?
Fibonacci Search is used to find an element in a sorted array by dividing the array into sections based on Fibonacci numbers.
Q2: Is Fibonacci Search faster than Binary Search?
Both have similar time complexity — O(log n). However, Fibonacci Search can be more efficient when data access time varies.
Q3: Can Fibonacci Search work on unsorted arrays?
No, Fibonacci Search only works correctly on sorted arrays.
Q4: Why should I learn Fibonacci Search?
It helps deepen your understanding of how mathematical sequences can optimize search algorithms.
Q5: Does Fibonacci Search use recursion or loops?
It can use either. Recursive versions are elegant, while iterative ones are generally more efficient.
Conclusion
Fibonacci Search is a fascinating algorithm that blends mathematics and programming into an efficient searching technique. By using Fibonacci numbers instead of midpoints, it introduces a unique way of dividing the search space.
In this article, we explored five Python programs — from basic iterative and recursive solutions to object-oriented and safe implementations. Each one builds upon the other, giving you a deeper understanding of how the algorithm works.
Keep experimenting with different arrays and inputs, and observe how Fibonacci Search behaves in various scenarios. The more you practice, the more confident you’ll become in writing efficient, elegant search algorithms in Python.
