Searching efficiently in a sorted array is a fundamental skill for every programmer. While Binary Search is the most popular method, there is another fascinating algorithm called Fibonacci Search, which uses Fibonacci numbers to divide the array and narrow down the search space. This algorithm is particularly useful because it reduces the number of comparisons in certain cases and works well for large datasets where accessing elements sequentially is costly.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is beginner-friendly because it combines simple mathematical ideas with practical searching techniques. By understanding how Fibonacci numbers determine the index to check, beginners can learn not only about searching but also about how math can optimize algorithms. It is widely applied in scenarios like database searching, memory-limited systems, and sorted lists where conventional Binary Search might not be ideal.
Program 1: Iterative Fibonacci Search
This program demonstrates Fibonacci Search using an iterative approach. It finds the closest Fibonacci number greater than or equal to the length of the array, then searches by reducing the range based on Fibonacci numbers.
open System
let fibonacciSearch (arr:int[]) key =
let n = arr.Length
let mutable fibMMm2 = 0
let mutable fibMMm1 = 1
let mutable fibM = fibMMm2 + fibMMm1
// Initialize fibonacci numbers
while fibM < n do
fibMMm2 <- fibMMm1
fibMMm1 <- fibM
fibM <- fibMMm2 + fibMMm1
let mutable offset = -1
let mutable foundIndex = -1
while fibM > 1 && foundIndex = -1 do
let i = min (offset + fibMMm2) (n - 1)
if arr.[i] < key then
fibM <- fibMMm1
fibMMm1 <- fibMMm2
fibMMm2 <- fibM - fibMMm1
offset <- i
elif arr.[i] > key then
fibM <- fibMMm2
fibMMm1 <- fibMMm1 - fibMMm2
fibMMm2 <- fibM - fibMMm1
else
foundIndex <- i
// Check last possible element
if foundIndex = -1 && fibMMm1 = 1 && offset + 1 < n && arr.[offset + 1] = key then
offset + 1
else
foundIndex
[<EntryPoint>]
let main argv =
let numbers = [| 1; 3; 5; 7; 9; 11; 13; 15 |]
let key = 11
let result = fibonacciSearch numbers key
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0In this program, the algorithm calculates the smallest Fibonacci number greater than the array length, then iteratively checks the index determined by Fibonacci numbers. Beginners can see how each comparison reduces the search range efficiently.
Program 2: Recursive Fibonacci Search
This program uses recursion to handle the Fibonacci Search process. Each recursive call reduces the array section to search based on Fibonacci numbers.
open System
let rec fibonacciSearchRec (arr:int[]) key fibM fibMMm1 fibMMm2 offset =
if fibM <= 1 then
if fibMMm1 = 1 && offset + 1 < arr.Length && arr.[offset + 1] = key then offset + 1
else -1
else
let i = min (offset + fibMMm2) (arr.Length - 1)
if arr.[i] < key then
fibonacciSearchRec arr key fibMMm1 fibMMm2 (fibM - fibMMm1) i
elif arr.[i] > key then
fibonacciSearchRec arr key fibMMm2 (fibMMm1 - fibMMm2) (fibM - fibMMm1) offset
else
i
[<EntryPoint>]
let main argv =
let numbers = [| 2; 4; 6; 8; 10; 12; 14 |]
let key = 10
let mutable fibMMm2 = 0
let mutable fibMMm1 = 1
let mutable fibM = fibMMm2 + fibMMm1
while fibM < numbers.Length do
fibMMm2 <- fibMMm1
fibMMm1 <- fibM
fibM <- fibMMm2 + fibMMm1
let result = fibonacciSearchRec numbers key fibM fibMMm1 fibMMm2 -1
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0This recursive approach helps beginners visualize how the Fibonacci numbers guide the index calculation and how the array is gradually reduced in size until the key is found.
Program 3: Fibonacci Search with Negative and Positive Numbers
Fibonacci Search works with arrays containing negative and positive numbers, as long as the array is sorted.
open System
let fibonacciSearchMixed (arr:int[]) key =
let n = arr.Length
let mutable fibMMm2 = 0
let mutable fibMMm1 = 1
let mutable fibM = fibMMm2 + fibMMm1
// Initialize fibonacci numbers
while fibM < n do
fibMMm2 <- fibMMm1
fibMMm1 <- fibM
fibM <- fibMMm2 + fibMMm1
let mutable offset = -1
let mutable foundIndex = -1
// Main loop
while fibM > 1 && foundIndex = -1 do
let i = min (offset + fibMMm2) (n - 1)
if arr.[i] < key then
fibM <- fibMMm1
fibMMm1 <- fibMMm2
fibMMm2 <- fibM - fibMMm1
offset <- i
elif arr.[i] > key then
fibM <- fibMMm2
fibMMm1 <- fibMMm1 - fibMMm2
fibMMm2 <- fibM - fibMMm1
else
foundIndex <- i
// Check last possible element
if foundIndex = -1 && fibMMm1 = 1 && offset + 1 < n && arr.[offset + 1] = key then
offset + 1
else
foundIndex
[<EntryPoint>]
let main argv =
let numbers = [| -20; -10; 0; 5; 10; 15; 20 |]
let key = -10
let result = fibonacciSearchMixed numbers key
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0This program shows that the Fibonacci Search logic applies to any sorted array, regardless of whether it contains negative or positive numbers.
Program 4: Fibonacci Search Returning Option Type
Using option types makes the result safer in F# and more idiomatic.
open System
let fibonacciSearchOption (arr:int[]) key =
let n = arr.Length
let mutable fibMMm2 = 0
let mutable fibMMm1 = 1
let mutable fibM = fibMMm2 + fibMMm1
// Initialize fibonacci numbers
while fibM < n do
fibMMm2 <- fibMMm1
fibMMm1 <- fibM
fibM <- fibMMm2 + fibMMm1
let mutable offset = -1
let mutable result : Option<int> = None
// Main loop
while fibM > 1 && result.IsNone do
let i = min (offset + fibMMm2) (n - 1)
if arr.[i] < key then
fibM <- fibMMm1
fibMMm1 <- fibMMm2
fibMMm2 <- fibM - fibMMm1
offset <- i
elif arr.[i] > key then
fibM <- fibMMm2
fibMMm1 <- fibMMm1 - fibMMm2
fibMMm2 <- fibM - fibMMm1
else
result <- Some i
// Check last possible element
if result.IsNone && fibMMm1 = 1 && offset + 1 < n && arr.[offset + 1] = key then
Some(offset + 1)
else
result
[<EntryPoint>]
let main argv =
let numbers = [| 1; 3; 5; 7; 9; 11 |]
let key = 7
match fibonacciSearchOption numbers key with
| Some index -> printfn "Element %d found at index %d" key index
| None -> printfn "Element %d not found" key
0Using option types encourages beginners to handle search results safely, avoiding ambiguous sentinel values.
Program 5: Step-by-Step Fibonacci Search
This program prints the Fibonacci numbers and indexes being checked to help beginners visualize the search.
open System
let fibonacciSearchStep (arr:int[]) key =
let n = arr.Length
let mutable fibMMm2 = 0
let mutable fibMMm1 = 1
let mutable fibM = fibMMm2 + fibMMm1
// Initialize fibonacci numbers
while fibM < n do
fibMMm2 <- fibMMm1
fibMMm1 <- fibM
fibM <- fibMMm2 + fibMMm1
let mutable offset = -1
let mutable foundIndex = -1
// Main loop with debug prints
while fibM > 1 && foundIndex = -1 do
let i = min (offset + fibMMm2) (n - 1)
printfn "Checking index %d" i
if arr.[i] < key then
fibM <- fibMMm1
fibMMm1 <- fibMMm2
fibMMm2 <- fibM - fibMMm1
offset <- i
elif arr.[i] > key then
fibM <- fibMMm2
fibMMm1 <- fibMMm1 - fibMMm2
fibMMm2 <- fibM - fibMMm1
else
foundIndex <- i
// Check last possible element
if foundIndex = -1 && fibMMm1 = 1 && offset + 1 < n && arr.[offset + 1] = key then
offset + 1
else
foundIndex
[<EntryPoint>]
let main argv =
let numbers = [| 1; 2; 4; 8; 16; 32 |]
let key = 16
let result = fibonacciSearchStep numbers key
if result <> -1 then
printfn "Element %d found at index %d" key result
else
printfn "Element %d not found" key
0Printing each checked index makes it easier for beginners to understand how Fibonacci numbers guide the search process.
Frequently Asked Questions (FAQ)
Q1. What is Fibonacci Search?
Fibonacci Search is a searching algorithm that uses Fibonacci numbers to divide the search space and locate a key in a sorted array.
Q2. Does the array need to be sorted?
Yes, a sorted array is required for Fibonacci Search to work correctly.
Q3. Can it handle negative numbers?
Yes, Fibonacci Search works with both negative and positive numbers as long as the array is sorted.
Q4. Why use Fibonacci Search instead of Binary Search?
Fibonacci Search may reduce comparisons in some cases, especially in large arrays or sequential-access data structures.
Q5. Is Fibonacci Search beginner-friendly?
Yes, it demonstrates how math and programming combine to optimize searches, making it a great learning algorithm for beginners.
Conclusion
Fibonacci Search is an efficient algorithm for searching sorted arrays, using Fibonacci numbers to guide the search process. Through multiple F# programs, we explored iterative and recursive approaches, handling negative numbers, returning option types, and printing step-by-step progress for better understanding.
For beginners, practicing Fibonacci Search strengthens knowledge of searching algorithms, recursion, and combining mathematical concepts with programming logic. Exploring different arrays and key values helps solidify understanding and prepares learners for more advanced search and optimization techniques.
