Searching for data is a fundamental task in computer programming. Whether you’re finding a name in a contact list, a record in a sorted database, or a specific value in an array, efficient searching is essential. While most beginners are familiar with algorithms like Linear Search or Binary Search, there is another interesting and efficient algorithm called Fibonacci Search.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is based on the famous Fibonacci sequence — a series of numbers where each number is the sum of the two preceding ones. The beauty of this algorithm lies in how it divides the search space using Fibonacci numbers instead of the middle element like Binary Search. This makes it especially useful in systems where the cost of accessing elements varies, such as in memory or database operations.
In this article, we’ll explore how to implement Fibonacci Search in Java. We’ll go step-by-step through six different programs that show the iterative, recursive, and optimized versions of the algorithm. Each program will be explained clearly so even a beginner can understand how Fibonacci Search works and how to apply it in real-world situations.
Program 1: Basic Iterative Fibonacci Search
Let’s start with the most straightforward way to implement Fibonacci Search in Java using loops. This version uses iteration to find the target element in a sorted array.
import java.util.*;
public class FibonacciSearchExample {
public static int fibonacciSearch(int[] arr, int x) {
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 = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
if (fibMMm1 == 1 && offset + 1 < n && arr[offset + 1] == x)
return offset + 1;
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90};
int target = 85;
int index = fibonacciSearch(arr, target);
if (index >= 0)
System.out.println("Element found at index: " + index);
else
System.out.println("Element not found");
}
}This program works by generating Fibonacci numbers until one is greater than or equal to the array length. It then uses these numbers to determine which range to search within. The algorithm reduces the search range in each step, similar to Binary Search, but using Fibonacci differences instead. It’s a great introduction to understanding how the Fibonacci sequence can guide efficient searching.
Program 2: Recursive Fibonacci Search
Now, let’s look at a recursive version of the Fibonacci Search. This approach replaces loops with recursive calls, giving the program a more mathematical structure.
import java.util.*;
public class RecursiveFibonacciSearch {
public static int fibonacciSearch(int[] arr, int x, int offset, int fibMMm2, int fibMMm1, int fibM) {
// Base case: no more Fibonacci numbers
if (fibM <= 1) return -1;
int i = Math.min(offset + fibMMm2, arr.length - 1);
if (arr[i] == x)
return i;
if (arr[i] < x) {
// Move 1 Fibonacci down
return fibonacciSearch(arr, x, i, fibMMm1 - fibMMm2, fibMMm2, fibMMm1);
} else {
// Move 2 Fibonacci down
return fibonacciSearch(arr, x, offset, fibMMm2 - (fibMMm1 - fibMMm2), fibMMm2, fibMMm1);
}
}
public static int startSearch(int[] arr, int x) {
int n = arr.length;
int fibMMm2 = 0; // (m-2)'th Fibonacci
int fibMMm1 = 1; // (m-1)'th Fibonacci
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
return fibonacciSearch(arr, x, -1, fibMMm2, fibMMm1, fibM);
}
public static void main(String[] args) {
int[] arr = {1, 3, 7, 15, 31, 63, 127};
int target = 31;
int index = startSearch(arr, target);
if (index >= 0)
System.out.println("Element found at index: " + index);
else
System.out.println("Element not found");
}
}This version works the same way as the iterative method but uses recursion to perform the search steps. Beginners will find it interesting how recursion simplifies the logic flow by calling the same method again with updated parameters. It’s a neat example of how mathematical concepts naturally fit into recursive programming.
Program 3: Simplified Fibonacci Search for Small Arrays
Here’s a more compact version of Fibonacci Search that’s great for testing and understanding the core idea using small datasets.
import java.util.*;
public class SimpleFibonacciSearch {
public static int search(int[] arr, int x) {
int n = arr.length;
int fibMMm2 = 0, fibMMm1 = 1, fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1) {
int i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 10, 15, 20, 25};
int target = 15;
int result = search(arr, target);
if (result >= 0)
System.out.println("Element found at index: " + result);
else
System.out.println("Element not found");
}
}This simpler version is ideal for small arrays and beginner-level learning. It focuses on the main algorithm logic without extra code, helping learners understand the sequence of comparisons that make Fibonacci Search so efficient.
Program 4: Fibonacci Search for Floating-Point Arrays
Fibonacci Search can also work with decimal numbers. This program demonstrates searching for a floating-point key in a sorted array.
public class FibonacciSearchFloat {
public static int fibonacciSearch(float[] arr, float key) {
int n = arr.length;
int fibMMm2 = 0;
int fibMMm1 = 1;
int fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm1 + fibMMm2;
}
int offset = -1;
while (fibM > 1) {
int i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < key) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > key) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
if (fibMMm1 == 1 && arr[offset + 1] == key) {
return offset + 1;
}
return -1;
}
public static void main(String[] args) {
float[] arr = {0.5f, 1.2f, 2.7f, 3.6f, 4.8f, 5.9f};
float key = 3.6f;
int index = fibonacciSearch(arr, key);
if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found in the array");
}
}This example demonstrates that Fibonacci Search is flexible and works with both integer and floating-point arrays, as long as the data is sorted. Beginners can see that the main logic remains unchanged, which emphasizes adaptability in programming.
Program 5: Object-Oriented Fibonacci Search Class
In this program, we wrap the Fibonacci Search logic inside a class to make it reusable and modular. This version is useful when you want to integrate Fibonacci Search into larger Java applications.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13};
int target = 9;
int result = FibonacciSearch.search(arr, target);
if (result >= 0)
System.out.println("Element found at index: " + result);
else
System.out.println("Element not found");
}
}
class FibonacciSearch {
public static int search(int[] arr, int x) {
int n = arr.length;
int fibMMm2 = 0, fibMMm1 = 1, fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1) {
int i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
if (fibMMm1 == 1 && offset + 1 < n && arr[offset + 1] == x)
return offset + 1;
return -1;
}
}This version is neat and object-oriented. The search logic is enclosed in a static method, which makes it easy to call without creating an object. It’s a professional and organized way to include Fibonacci Search in Java projects.
Program 6: Fibonacci Search with Error Handling
Finally, let’s add a layer of safety. This version handles invalid inputs like empty arrays gracefully, which is important in real-world programming.
import java.util.*;
public class SafeFibonacciSearch {
public static int search(int[] arr, int x) {
if (arr == null || arr.length == 0) return -1;
int n = arr.length;
int fibMMm2 = 0, fibMMm1 = 1, fibM = fibMMm2 + fibMMm1;
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
int offset = -1;
while (fibM > 1) {
int i = Math.min(offset + fibMMm2, n - 1);
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
} else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
} else {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {};
int target = 20;
int result = search(arr, target);
if (result >= 0)
System.out.println("Element found at index: " + result);
else
System.out.println("Element not found");
}
}This final version is robust and handles real-world conditions gracefully. It ensures that your program won’t crash when given invalid or empty inputs, which is a good habit for every beginner programmer to develop early on.
Frequently Asked Questions (FAQ)
This section answers common questions beginners often ask about Fibonacci Search in Java.
Q1: What is Fibonacci Search used for?
Fibonacci Search is used to efficiently find an element in a sorted array by dividing the range based on Fibonacci numbers.
Q2: Is Fibonacci Search better than Binary Search?
Both have similar time complexity (O(log n)), but Fibonacci Search can be better in systems with non-uniform memory access times.
Q3: Can Fibonacci Search work on unsorted data?
No. Like Binary Search, it only works correctly on sorted arrays.
Q4: Why should I learn Fibonacci Search?
It’s a great algorithm for understanding optimization and how mathematical concepts like the Fibonacci sequence can improve program efficiency.
Q5: Does Fibonacci Search use recursion or iteration?
It can be implemented both ways. Recursive versions are elegant, while iterative ones are usually more memory-efficient.
Conclusion
Fibonacci Search is a wonderful example of how mathematics and programming blend to create efficient solutions. By using Fibonacci numbers to divide the search range, it provides an alternative to Binary Search that can be more suitable in certain environments.
Through this article, we’ve explored six Java programs — from simple iterative solutions to recursive and safe versions. Each program demonstrates a new layer of understanding, helping you grasp both the logic and the elegance behind Fibonacci Search.
Keep practicing these examples, try modifying them with your own arrays, and explore how Fibonacci Search performs in different scenarios. The more you experiment, the deeper your understanding of algorithms will grow — and that’s what makes learning programming truly exciting.
