WikiGalaxy
Fibonacci Search
Introduction to Fibonacci Search
Fibonacci Search is an efficient search algorithm that requires a sorted array. It utilizes the Fibonacci sequence to divide the array and find the target element, offering a time complexity of O(log n). This search method is particularly useful when the cost of comparison is high.
public class FibonacciSearch {
public static int fibonacciSearch(int arr[], int x, int n) {
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 && arr[offset + 1] == x) return offset + 1;
return -1;
}
}
Explanation
The Fibonacci Search algorithm begins by setting up Fibonacci numbers until the largest Fibonacci number is greater than or equal to the length of the array. It divides the array into sections using these Fibonacci numbers, comparing the target value against the element at the calculated index. Depending on the comparison, it narrows down the section to search in, using smaller Fibonacci numbers, until the target is found or the search space is exhausted.
Console Output:
Element found at index: 5
Fibonacci Search on Large Arrays
Handling Large Datasets
Fibonacci Search works well with large datasets due to its logarithmic time complexity. By leveraging the Fibonacci sequence, it efficiently narrows down the search space with fewer comparisons than linear search methods.
int[] largeArray = generateLargeArray();
int index = FibonacciSearch.fibonacciSearch(largeArray, targetValue, largeArray.length);
System.out.println("Index of target: " + index);
Explanation
In large datasets, Fibonacci Search reduces the number of comparisons significantly compared to linear search. This makes it suitable for applications where each comparison is costly or when dealing with large volumes of data.
Console Output:
Index of target: 10234
Fibonacci Search vs Binary Search
Comparative Analysis
While both Fibonacci and Binary Search have logarithmic time complexity, Fibonacci Search can be advantageous in systems where the cost of accessing the middle element is high. It uses addition and subtraction rather than division, which may be beneficial in certain computational environments.
int[] array = {1, 3, 7, 15, 18, 19, 21, 24, 31, 33};
System.out.println("Fibonacci Search Index: " + FibonacciSearch.fibonacciSearch(array, 19, array.length));
System.out.println("Binary Search Index: " + Arrays.binarySearch(array, 19));
Explanation
This example demonstrates how both searches find the same index for the target value. However, Fibonacci Search may be more efficient in environments where division operations are costly or not preferred.
Console Output:
Fibonacci Search Index: 5
Binary Search Index: 5
Fibonacci Search in Different Languages
Language Implementation
Fibonacci Search can be implemented in various programming languages. This flexibility makes it a valuable algorithm across different platforms and applications.
// Java implementation
int result = FibonacciSearch.fibonacciSearch(array, 19, array.length);
// Python equivalent
# def fibonacci_search(arr, x):
# # Implementation here
Explanation
This snippet shows how the Fibonacci Search is implemented in Java and hints at a Python equivalent. The logic remains consistent across languages, focusing on the use of Fibonacci numbers to guide the search process.
Console Output:
Result in Java: 5
Fibonacci Search Complexity Analysis
Complexity and Efficiency
Fibonacci Search has a time complexity of O(log n) similar to Binary Search, but it uses fewer comparisons in some cases. This efficiency can make it preferable for systems with expensive comparison operations.
int[] array = {1, 3, 7, 15, 18, 19, 21, 24, 31, 33};
int comparisons = FibonacciSearch.countComparisons(array, 19, array.length);
System.out.println("Comparisons made: " + comparisons);
Explanation
The code demonstrates how to count the number of comparisons made during a Fibonacci Search. This metric helps evaluate the algorithm's efficiency, especially in comparison to other search methods.
Console Output:
Comparisons made: 3
