Fibonacci Search is an interesting and efficient searching algorithm for sorted arrays, built on the principles of the Fibonacci sequence. Unlike binary search, which splits the array in half, Fibonacci Search uses Fibonacci numbers to divide the array into sections, which can sometimes provide faster search performance, especially in systems where arithmetic operations are expensive.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, implementing Fibonacci Search in Rust is a great way to learn about array traversal, index calculations, and the importance of using mathematical sequences in algorithms. This method is often used in database search systems, numerical datasets, or any scenario where a sorted array needs quick searching. Practicing it helps you understand how mathematical patterns can optimize real-world computations.
Program 1: Iterative Fibonacci Search on Integers
This program demonstrates a simple, iterative implementation of Fibonacci Search on a sorted array of integers. It calculates the required Fibonacci numbers to find the position of the target.
fn fibonacci_search(arr: &[i32], target: i32) -> Option<usize> {
let n = arr.len();
let mut fib2 = 0;
let mut fib1 = 1;
let mut fib = fib1 + fib2;
while fib < n {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let mut offset = -1isize;
while fib > 1 {
let i = std::cmp::min((offset + fib2 as isize) as usize, n - 1);
if arr[i] < target {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i as isize;
} else if arr[i] > target {
fib = fib2;
fib1 -= fib2;
fib2 = fib - fib1;
} else {
return Some(i);
}
}
if fib1 == 1 && (offset + 1) < n as isize && arr[(offset + 1) as usize] == target {
return Some((offset + 1) as usize);
}
None
}
fn main() {
let numbers = [10, 22, 35, 40, 45, 50, 80, 82, 85];
let target = 45;
println!("Array: {:?}", numbers);
match fibonacci_search(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}This program iteratively calculates Fibonacci numbers to find sections of the array to search. Beginners can see how arithmetic and index management combine to locate the target efficiently.
Program 2: Recursive Fibonacci Search
Here, Fibonacci Search is implemented recursively, showing how recursion can simplify the logic while keeping the Fibonacci index calculations clear.
fn fibonacci_search_recursive(arr: &[i32], target: i32) -> Option<usize> {
fn helper(arr: &[i32], target: i32, fib2: usize, fib1: usize, offset: isize) -> Option<usize> {
if fib1 == 0 { return None; }
let i = std::cmp::min((offset + fib2 as isize) as usize, arr.len() - 1);
if arr[i] < target {
return helper(arr, target, fib1 - fib2, fib2, i as isize);
} else if arr[i] > target {
return helper(arr, target, fib2 - (fib1 - fib2), fib2, offset);
} else {
return Some(i);
}
}
let mut fib2 = 0;
let mut fib1 = 1;
let mut fib = fib1 + fib2;
while fib < arr.len() {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
helper(arr, target, fib2, fib1, -1)
}
fn main() {
let numbers = [5, 10, 15, 20, 25, 30, 35];
let target = 20;
println!("Array: {:?}", numbers);
match fibonacci_search_recursive(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Recursion in this program demonstrates how the search interval can be refined without explicit loops. Beginners can understand the power of dividing problems into smaller, manageable subproblems.
Program 3: Fibonacci Search on Floating-Point Numbers
Fibonacci Search can also work with floating-point numbers, but careful comparisons are required to avoid precision issues.
fn fibonacci_search_floats(arr: &[f64], target: f64) -> Option<usize> {
let n = arr.len();
let mut fib2 = 0;
let mut fib1 = 1;
let mut fib = fib1 + fib2;
while fib < n {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let mut offset = -1isize;
while fib > 1 {
let i = std::cmp::min((offset + fib2 as isize) as usize, n - 1);
if arr[i] < target {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i as isize;
} else if arr[i] > target {
fib = fib2;
fib1 -= fib2;
fib2 = fib - fib1;
} else {
return Some(i);
}
}
if fib1 == 1 && (offset + 1) < n as isize && (arr[(offset + 1) as usize] - target).abs() < std::f64::EPSILON {
return Some((offset + 1) as usize);
}
None
}
fn main() {
let numbers = [1.1, 2.2, 3.3, 4.4, 5.5, 6.6];
let target = 4.4;
println!("Array: {:?}", numbers);
match fibonacci_search_floats(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}This program highlights the importance of using a small threshold (EPSILON) for floating-point comparisons. Beginners learn to adapt algorithms for different data types.
Program 4: Fibonacci Search with Debug Prints
Adding debug prints helps visualize how the search interval and Fibonacci indices change during the search process.
fn fibonacci_search_debug(arr: &[i32], target: i32) -> Option<usize> {
let n = arr.len();
let mut fib2 = 0;
let mut fib1 = 1;
let mut fib = fib1 + fib2;
while fib < n {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let mut offset = -1isize;
while fib > 1 {
let i = std::cmp::min((offset + fib2 as isize) as usize, n - 1);
println!("Checking index {}: {}", i, arr[i]);
if arr[i] < target {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i as isize;
} else if arr[i] > target {
fib = fib2;
fib1 -= fib2;
fib2 = fib - fib1;
} else {
return Some(i);
}
}
if fib1 == 1 && (offset + 1) < n as isize && arr[(offset + 1) as usize] == target {
return Some((offset + 1) as usize);
}
None
}
fn main() {
let numbers = [11, 22, 33, 44, 55, 66];
let target = 44;
println!("Array: {:?}", numbers);
match fibonacci_search_debug(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}Debug prints allow beginners to trace each step, showing how the Fibonacci numbers guide the search interval, which helps in learning and debugging.
Program 5: Optimized Fibonacci Search with Early Exit
This version quickly exits if the target is outside the array bounds, making it more efficient for large arrays.
fn fibonacci_search_early_exit(arr: &[i32], target: i32) -> Option<usize> {
if arr.is_empty() || target < arr[0] || target > arr[arr.len() - 1] {
return None;
}
let n = arr.len();
let mut fib2 = 0;
let mut fib1 = 1;
let mut fib = fib1 + fib2;
while fib < n {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let mut offset = -1isize;
while fib > 1 {
let i = std::cmp::min((offset + fib2 as isize) as usize, n - 1);
if arr[i] < target {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i as isize;
} else if arr[i] > target {
fib = fib2;
fib1 -= fib2;
fib2 = fib - fib1;
} else {
return Some(i);
}
}
if fib1 == 1 && (offset + 1) < n as isize && arr[(offset + 1) as usize] == target {
return Some((offset + 1) as usize);
}
None
}
fn main() {
let numbers = [7, 14, 21, 28, 35, 42];
let target = 50;
println!("Array: {:?}", numbers);
match fibonacci_search_early_exit(&numbers, target) {
Some(idx) => println!("Element {} found at index {}", target, idx),
None => println!("Element {} not found", target),
}
}This version prevents unnecessary calculations if the target is clearly outside the array, which is a good practice for efficiency.
Frequently Asked Questions (FAQ)
Q1: What is the time complexity of Fibonacci Search?
It runs in O(log n), similar to binary search, since each iteration reduces the search space roughly by a Fibonacci number.
Q2: Can Fibonacci Search be used on unsorted arrays?
No, the array must be sorted for correct results.
Q3: How does it differ from Binary Search?
Binary Search splits the array in half, while Fibonacci Search splits it using Fibonacci numbers, which can optimize index calculations in certain systems.
Q4: Can it handle floating-point numbers?
Yes, but comparisons should use a small threshold (EPSILON) to account for floating-point precision.
Q5: Is Fibonacci Search iterative or recursive?
It can be implemented both ways. Iterative is often more memory-efficient, while recursive code can be clearer for learning purposes.
Conclusion
Fibonacci Search is an elegant algorithm for efficiently locating elements in sorted arrays, using the Fibonacci sequence to guide the search. Implementing it in Rust teaches beginners about array traversal, index calculations, and the interplay between mathematics and programming. By practicing iterative, recursive, and floating-point versions, as well as adding debug prints or early exit optimizations, beginners can gain a strong grasp of how algorithm design improves performance and understanding. Exploring this method encourages learners to experiment with other sequence-based algorithms and deepen their Rust programming skills.
