Fibonacci Search is a unique search algorithm that uses Fibonacci numbers to divide a sorted array into sections and find a target element. Unlike Binary Search, which splits the array in half, Fibonacci Search divides the array based on Fibonacci numbers, which can provide better performance in certain cases, especially when accessing elements is costly. It is particularly useful for large sorted datasets where sequential memory access is preferred, such as in databases or memory-constrained systems.
with hands-on learning.
get the skills and confidence to land your next move.
Learning Fibonacci Search in Scala helps beginners explore a less common but powerful search method. It also reinforces concepts like recursion, iteration, and array manipulation, while offering an alternative approach to understanding search algorithms beyond the standard Linear and Binary Search methods.
Program 1: Basic Fibonacci Search
This program demonstrates the basic iterative approach to Fibonacci Search on a sorted integer array.
object FibonacciSearchBasic {
def fibSearch(arr: Array[Int], target: Int): Int = {
var fibMMm2 = 0
var fibMMm1 = 1
var fibM = fibMMm2 + fibMMm1
while (fibM < arr.length) {
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
}
var offset = -1
while (fibM > 1) {
val i = Math.min(offset + fibMMm2, arr.length - 1)
if (arr(i) < target) {
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
} else if (arr(i) > target) {
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
} else return i
}
if (fibMMm1 == 1 && arr(offset + 1) == target) offset + 1
else -1
}
def main(args: Array[String]): Unit = {
val data = Array(1, 3, 5, 7, 9, 11, 13)
val target = 7
val index = fibSearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This example shows how Fibonacci numbers guide the search, creating smaller subarrays to efficiently locate the target. Beginners can see how offset and Fibonacci numbers work together to navigate the array.
Program 2: Recursive Fibonacci Search
This program implements Fibonacci Search using recursion for range selection.
object FibonacciSearchRecursive {
def fibSearchRec(arr: Array[Int], target: Int, fibM: Int, fibMMm1: Int, fibMMm2: Int, offset: Int): Int = {
if (fibM == 0) return -1
val i = Math.min(offset + fibMMm2, arr.length - 1)
if (arr(i) == target) return i
else if (arr(i) < target) {
fibSearchRec(arr, target, fibMMm1, fibMMm2, fibMMm1 - fibMMm2, i)
} else {
fibSearchRec(arr, target, fibMMm2, fibMMm1 - fibMMm2, fibMMm2 - (fibMMm1 - fibMMm2), offset)
}
}
def main(args: Array[String]): Unit = {
val data = Array(2, 4, 6, 8, 10, 12, 14)
var fibMMm2 = 0
var fibMMm1 = 1
var fibM = fibMMm2 + fibMMm1
while (fibM < data.length) {
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
}
val target = 10
val index = fibSearchRec(data, target, fibM, fibMMm1, fibMMm2, -1)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}Recursive Fibonacci Search highlights how breaking down the array with Fibonacci numbers can be expressed elegantly with function calls. Beginners learn to combine recursion with search logic effectively.
Program 3: Fibonacci Search for Floating-Point Arrays
Fibonacci Search is versatile and can be applied to arrays with decimal values.
object FibonacciSearchFloat {
def fibSearch(arr: Array[Double], target: Double): Int = {
var fibMMm2 = 0
var fibMMm1 = 1
var fibM = fibMMm2 + fibMMm1
while (fibM < arr.length) {
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
}
var offset = -1
while (fibM > 1) {
val i = Math.min(offset + fibMMm2, arr.length - 1)
if (arr(i) < target) {
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
} else if (arr(i) > target) {
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
} else return i
}
if (fibMMm1 == 1 && arr(offset + 1) == target) offset + 1
else -1
}
def main(args: Array[String]): Unit = {
val data = Array(1.5, 2.5, 3.5, 4.5, 5.5)
val target = 4.5
val index = fibSearch(data, target)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This program shows that Fibonacci Search works with sorted decimal arrays, making it suitable for real-world applications involving non-integer values.
Program 4: Fibonacci Search with Multiple Occurrences
This program adapts Fibonacci Search to find all indices of a target in arrays with duplicates.
object FibonacciSearchMultiple {
def fibSearchAll(arr: Array[Int], target: Int): Array[Int] = {
var fibMMm2 = 0
var fibMMm1 = 1
var fibM = fibMMm2 + fibMMm1
while (fibM < arr.length) {
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
}
var offset = -1
val indices = scala.collection.mutable.ArrayBuffer[Int]()
while (fibM > 1) {
val i = Math.min(offset + fibMMm2, arr.length - 1)
if (arr(i) < target) {
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
} else if (arr(i) > target) {
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
} else {
indices += i
var j = i - 1
while (j >= 0 && arr(j) == target) { indices += j; j -= 1 }
j = i + 1
while (j < arr.length && arr(j) == target) { indices += j; j += 1 }
return indices.sorted.toArray
}
}
if (fibMMm1 == 1 && arr(offset + 1) == target) Array(offset + 1)
else indices.toArray
}
def main(args: Array[String]): Unit = {
val data = Array(1, 2, 2, 2, 3, 4)
val target = 2
val indices = fibSearchAll(data, target)
if (indices.nonEmpty) println(s"Element $target found at indices: ${indices.mkString(", ")}")
else println(s"Element $target not found")
}
}This teaches beginners how to extend Fibonacci Search for arrays with repeated elements, collecting multiple indices efficiently.
Program 5: Recursive Fibonacci Search for Floating-Point Arrays
This program combines recursion and floating-point data to show versatility.
object FibonacciSearchFloatRecursive {
def fibSearchRec(arr: Array[Double], target: Double, fibM: Int, fibMMm1: Int, fibMMm2: Int, offset: Int): Int = {
if (fibM == 0) return -1
val i = Math.min(offset + fibMMm2, arr.length - 1)
if (arr(i) == target) return i
else if (arr(i) < target) fibSearchRec(arr, target, fibMMm1, fibMMm2, fibMMm1 - fibMMm2, i)
else fibSearchRec(arr, target, fibMMm2, fibMMm1 - fibMMm2, fibMMm2 - (fibMMm1 - fibMMm2), offset)
}
def main(args: Array[String]): Unit = {
val data = Array(1.1, 2.2, 3.3, 4.4, 5.5)
var fibMMm2 = 0
var fibMMm1 = 1
var fibM = fibMMm2 + fibMMm1
while (fibM < data.length) { fibMMm2 = fibMMm1; fibMMm1 = fibM; fibM = fibMMm2 + fibMMm1 }
val target = 3.3
val index = fibSearchRec(data, target, fibM, fibMMm1, fibMMm2, -1)
if (index != -1) println(s"Element $target found at index $index")
else println(s"Element $target not found")
}
}This shows that recursion and floating-point data can be combined for a clean, efficient implementation.
Frequently Asked Questions (FAQ)
This section answers common questions beginners may have about Fibonacci Search in Scala.
Q1: What is Fibonacci Search?
Fibonacci Search uses Fibonacci numbers to divide a sorted array and locate a target efficiently.
Q2: When is Fibonacci Search better than Binary Search?
It is more efficient when accessing sequential memory is costly, or the dataset is very large.
Q3: Can Fibonacci Search handle floating-point arrays?
Yes, as long as the array is sorted.
Q4: Can Fibonacci Search find multiple occurrences of a value?
Yes, by collecting all indices during the search phase.
Q5: Why learn Fibonacci Search in Scala?
It teaches advanced search logic, recursion, and array manipulation, providing a deeper understanding of algorithm efficiency.
Conclusion
Fibonacci Search is an elegant and efficient algorithm for searching sorted arrays using Fibonacci numbers to guide the search. Through iterative and recursive implementations, handling integers, floating-point numbers, and multiple occurrences, beginners can see how it works in different scenarios. Practicing these programs strengthens problem-solving skills and gives confidence in using alternative search techniques in Scala.
