Searching is one of the most common tasks in computer programming. Whether you’re looking for a name in a contact list, a product in a sorted catalog, or a number in an array, an efficient search algorithm can make all the difference. One of the lesser-known yet fascinating searching techniques 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 term is the sum of the two preceding ones. This algorithm divides the search range using Fibonacci numbers, similar to how Binary Search divides the range in half. What makes Fibonacci Search unique is that it works well for large, sorted datasets and can be useful in situations where accessing elements is costly, such as in memory-limited systems.
In this article, we’ll explore how to implement Fibonacci Search in Dart. We’ll go through several versions of the program—from simple iterative methods to recursive and optimized approaches. By the end, you’ll not only understand the logic behind Fibonacci Search but also feel confident enough to use it in your own Dart projects.
Program 1: Basic Fibonacci Search Using Iteration
This first program introduces the simplest way to perform a Fibonacci Search using iteration. It finds the smallest Fibonacci number greater than or equal to the length of the array and uses that to locate the target element.
import 'dart:math';
int fibonacciSearch(List<int> arr, int target) {
int n = arr.length;
int fibMMm2 = 0; // (m-2)'th Fibonacci number
int fibMMm1 = 1; // (m-1)'th Fibonacci number
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci number
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1) {
int i = min(offset + fibMMm2, n - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > target) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
if (fibMMm1 == 1 && offset + 1 < n && arr[offset + 1] == target) {
return offset + 1;
}
return -1;
}
void main() {
List<int> arr = [1, 3, 5, 7, 9, 11, 13];
int target = 9;
int result = fibonacciSearch(arr, target);
if (result != -1) {
print("Element $target found at index $result");
} else {
print("Element $target not found");
}
}This version builds the Fibonacci numbers until one of them exceeds the array size. It then narrows down the possible search range by comparing the target value against midpoints defined by Fibonacci indices. This iterative approach is efficient and easy to follow, making it perfect for beginners.
Program 2: Recursive Fibonacci Search
Now, let’s move to a recursive approach where we rely on function calls instead of loops. Recursion makes the code elegant and easier to understand for those familiar with recursive logic.
import 'dart:math';
int fibonacciSearchRecursive(List<int> arr, int target, int offset, int fibMMm2, int fibMMm1, int fibM) {
if (fibM == 0) return -1;
// Check safe index
int i = min(offset + fibMMm2, arr.length - 1);
if (arr[i] == target) {
return i;
} else if (arr[i] < target) {
// Move to the right subarray
return fibonacciSearchRecursive(arr, target, i + 1, fibMMm1 - fibMMm2, fibMMm2, fibMMm1);
} else {
// Move to the left subarray
return fibonacciSearchRecursive(arr, target, offset, fibMMm2, fibMMm1 - fibMMm2, fibMMm2);
}
}
int startRecursiveSearch(List<int> arr, int target) {
int n = arr.length;
// Initialize first 2 Fibonacci numbers
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
// Find the smallest Fibonacci number >= n
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
return fibonacciSearchRecursive(arr, target, 0, fibMMm2, fibMMm1, fibM);
}
void main() {
List<int> arr = [2, 4, 8, 16, 32, 64, 128];
int target = 16;
int result = startRecursiveSearch(arr, target);
if (result != -1) {
print("Element $target found at index $result");
} else {
print("Element $target not found");
}
}This version applies the same logic as before but uses recursion to handle range divisions. It helps beginners understand how Fibonacci Search naturally fits into recursive problem-solving patterns, offering both simplicity and mathematical beauty.
Program 3: Simplified Version for Small Arrays
In this example, we simplify the Fibonacci Search for smaller datasets to make it easier for beginners to test and understand the algorithm’s step-by-step process.
import 'dart:math';
int simpleFibonacciSearch(List<int> arr, int target) {
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
while (fibM < arr.length) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1) {
int i = min(offset + fibMMm2, arr.length - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > target) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
return -1;
}
void main() {
List<int> arr = [10, 20, 30, 40, 50];
int target = 30;
int index = simpleFibonacciSearch(arr, target);
if (index != -1) {
print("Element $target found at index $index");
} else {
print("Element $target not found");
}
}This version is concise and perfect for small test arrays. It’s ideal for beginners who want to focus on the logic without being distracted by complex conditions or large datasets.
Program 4: Modular Fibonacci Search Function
Here we make the search logic modular so that it can be reused in any Dart program easily.
import 'dart:math';
class FibonacciSearch {
static int search(List<int> arr, int target) {
int n = arr.length;
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1) {
int i = min(offset + fibMMm2, n - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > target) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
if (fibMMm1 == 1 && offset + 1 < n && arr[offset + 1] == target) {
return offset + 1;
}
return -1;
}
}
void main() {
List<int> data = [1, 2, 3, 5, 8, 13, 21];
int target = 8;
int result = FibonacciSearch.search(data, target);
if (result != -1) {
print("Element $target found at index $result");
} else {
print("Element $target not found");
}
}This reusable design is great for developers who want clean and modular code. You can call FibonacciSearch.search() in any program, making your Dart projects more organized and maintainable.
Program 5: Safe Fibonacci Search with Error Handling
In real-world applications, input errors happen. This version includes error handling to ensure that the algorithm behaves correctly even when the list is empty or invalid.
import 'dart:math';
int safeFibonacciSearch(List<int>? arr, int target) {
if (arr == null || arr.isEmpty) return -1;
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
while (fibM < arr.length) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1) {
int i = min(offset + fibMMm2, arr.length - 1);
if (arr[i] < target) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > target) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
return -1;
}
void main() {
List<int>? arr = [2, 4, 6, 8, 10];
int target = 7;
int result = safeFibonacciSearch(arr, target);
if (result != -1) {
print("Element $target found at index $result");
} else {
print("Element $target not found");
}
}This safe version prevents crashes due to null or empty inputs. It’s especially useful when dealing with real-world data or user inputs where conditions might not always be ideal.
Frequently Asked Questions (FAQ)
This section answers common questions that beginners often have about Fibonacci Search.
Q1: What is Fibonacci Search used for?
Fibonacci Search is used to search elements in sorted arrays. It is particularly useful when data is stored in structures where accessing sequential elements is more efficient than random access.
Q2: How is Fibonacci Search different from Binary Search?
While Binary Search splits the array into halves, Fibonacci Search divides it based on Fibonacci numbers, which can be more efficient in certain systems.
Q3: Can Fibonacci Search work on unsorted data?
No, Fibonacci Search only works correctly on sorted data.
Q4: Is Fibonacci Search faster than Binary Search?
In most cases, both have similar time complexity (O(log n)), but Fibonacci Search may have an advantage when dealing with sequential memory access.
Q5: Why should I learn Fibonacci Search?
Learning Fibonacci Search helps you understand algorithm optimization and gives you a deeper appreciation for how mathematics and programming combine beautifully.
Conclusion
Fibonacci Search is an elegant algorithm that blends mathematical beauty with computational efficiency. By dividing the search space using Fibonacci numbers, it offers an alternative approach to traditional searching methods.
Through the programs we’ve explored, you’ve seen how to implement Fibonacci Search in Dart using both iterative and recursive methods, handle errors, and write reusable code. The best way to learn is by experimenting—try modifying these examples, change the data, and observe how the algorithm behaves.
With practice, you’ll not only master Fibonacci Search but also strengthen your understanding of algorithm design and efficiency in Dart programming. Keep coding, stay curious, and enjoy your programming journey!
