Fibonacci Search is a divide-and-conquer algorithm similar to Binary Search, but it uses Fibonacci numbers to divide the array into search segments. It is particularly efficient for sorted arrays when the dataset size is large and the cost of accessing elements is high (e.g., accessing memory hierarchies or disk storage).
How Fibonacci Search Works?
- Generate the smallest Fibonacci number greater than or equal to the size of the array.
- Use the Fibonacci sequence to divide the array into sections.
- Compare the key with the element at the calculated index (
fibIndex).- If the key matches, return the index.
- If the key is smaller, move to the left subarray.
- If the key is larger, move to the right subarray.
- Repeat until the subarray size reduces to one.
- If the key is not found, return
-1.
Fibonacci Search in Java Examples
This article covers Fibonacci Search with two Java examples: a basic program for arrays and an advanced program for searching in lists of custom objects, highlighting its practical applications.
1. Fibonacci Search Java Program (Basic example)
This example program demonstrates the Fibonacci Search for a sorted array of integers.
package com.javacodepoint.search;
public class BasicFibonacciSearch {
public static int fibonacciSearch(int[] array, int key) {
int n = array.length;
// Initialize Fibonacci numbers
int fib2 = 0; // (m-2)'th Fibonacci number
int fib1 = 1; // (m-1)'th Fibonacci number
int fibM = fib2 + fib1; // m'th Fibonacci number
// Find the smallest Fibonacci number greater than or equal to n
while (fibM < n) {
fib2 = fib1;
fib1 = fibM;
fibM = fib2 + fib1;
}
// Marks the eliminated range from the front
int offset = -1;
while (fibM > 1) {
int i = Math.min(offset + fib2, n - 1);
// Compare key with array[i]
if (array[i] < key) {
fibM = fib1;
fib1 = fib2;
fib2 = fibM - fib1;
offset = i;
} else if (array[i] > key) {
fibM = fib2;
fib1 = fib1 - fib2;
fib2 = fibM - fib1;
} else {
return i; // Key found
}
}
// Check the last element
if (fib1 == 1 && array[offset + 1] == key) {
return offset + 1;
}
return -1; // Key not found
}
public static void main(String[] args) {
int[] numbers = { 10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100 };
int key = 85;
int result = fibonacciSearch(numbers, key);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found.");
}
}
}
OUTPUT:
Element found at index: 8
2. Fibonacci Search Advanced Program Example
This advanced Java program example demonstrates the Fibonacci Search algorithm applied to a list of custom objects, specifically a list of Book objects. The search is performed based on the id property of each Book.
The program first calculates the smallest Fibonacci number greater than or equal to the list size and then uses Fibonacci-based segmentation to locate the desired Book. If a match is found, the program returns the index and details of the Book. The list is sorted by id to ensure the algorithm’s prerequisites are met. This approach showcases the adaptability of Fibonacci Search for real-world scenarios involving complex data structures.
package com.javacodepoint.search;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
class Book {
private int id;
private String title;
public Book(int id, String title) {
this.id = id;
this.title = title;
}
public int getId() {
return id;
}
@Override
public String toString() {
return "Book{id=" + id + ", title='" + title + "'}";
}
}
public class AdvancedFibonacciSearch {
public static int fibonacciSearch(List<Book> books, int key) {
int n = books.size();
// Initialize Fibonacci numbers
int fib2 = 0;
int fib1 = 1;
int fibM = fib2 + fib1;
// Find the smallest Fibonacci number greater than or equal to n
while (fibM < n) {
fib2 = fib1;
fib1 = fibM;
fibM = fib2 + fib1;
}
int offset = -1;
while (fibM > 1) {
int i = Math.min(offset + fib2, n - 1);
if (books.get(i).getId() < key) {
fibM = fib1;
fib1 = fib2;
fib2 = fibM - fib1;
offset = i;
} else if (books.get(i).getId() > key) {
fibM = fib2;
fib1 = fib1 - fib2;
fib2 = fibM - fib1;
} else {
return i; // Key found
}
}
if (fib1 == 1 && books.get(offset + 1).getId() == key) {
return offset + 1;
}
return -1; // Key not found
}
public static void main(String[] args) {
List<Book> books = new ArrayList<>();
books.add(new Book(101, "Java Basics"));
books.add(new Book(102, "Data Structures"));
books.add(new Book(103, "Algorithms"));
books.add(new Book(104, "Design Patterns"));
int key = 103;
// Sort books by ID
books.sort(Comparator.comparingInt(Book::getId));
int result = fibonacciSearch(books, key);
if (result != -1) {
System.out.println("Book found: " + books.get(result));
} else {
System.out.println("Book not found.");
}
}
}
OUTPUT:
Book found: Book{id=103, title=’Algorithms’}
Key Points About Fibonacci Search
- Requirements: Works only on sorted datasets.
- Efficiency: Time complexity is O(logn).
- Use Case: Best suited for datasets where Binary Search’s fixed divisions are suboptimal.
To deepen your understanding of data structures and algorithms, consider exploring other searching techniques like Linear Search, Binary Search, Interpolation Search, Exponential Search, Ternary Search, and Jump Search.