Searching efficiently is a crucial skill in programming, and there are several algorithms designed to help us find elements quickly in sorted data. One interesting and slightly different approach is the Fibonacci Search. This algorithm is based on Fibonacci numbers, which are a sequence of numbers where each number is the sum of the two preceding ones. Fibonacci Search uses these numbers to divide a sorted array into segments, allowing it to efficiently locate the target element.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is particularly useful when working with large, sorted datasets, and it can be more efficient than Binary Search in some situations. For Kotlin beginners, implementing Fibonacci Search is a great way to learn how mathematical sequences can be applied to algorithm design. This also introduces the idea of divide-and-conquer in a different way than traditional methods.
Program 1: Iterative Fibonacci Search on Array
This program demonstrates the classic iterative approach to Fibonacci Search on a simple array of integers.
fun fibonacciSearch(arr: IntArray, target: Int): Int {
val n = arr.size
var fibMm2 = 0 // (m-2)'th Fibonacci number
var fibMm1 = 1 // (m-1)'th Fibonacci number
var fibM = fibMm2 + fibMm1 // m'th Fibonacci number
while (fibM < n) {
fibMm2 = fibMm1
fibMm1 = fibM
fibM = fibMm1 + fibMm2
}
var offset = -1
while (fibM > 1) {
val i = minOf(offset + fibMm2, n - 1)
when {
arr[i] < target -> {
fibM = fibMm1
fibMm1 = fibMm2
fibMm2 = fibM - fibMm1
offset = i
}
arr[i] > target -> {
fibM = fibMm2
fibMm1 -= fibMm2
fibMm2 = fibM - fibMm1
}
else -> return i
}
}
return if (fibMm1 == 1 && offset + 1 < n && arr[offset + 1] == target) offset + 1 else -1
}
fun main() {
val numbers = intArrayOf(5, 10, 15, 20, 25, 30, 35)
val target = 20
println("Array: ${numbers.joinToString()}")
val index = fibonacciSearch(numbers, target)
if (index != -1) println("Element $target found at index $index")
else println("Element $target not found")
}In this program, the array is split using Fibonacci numbers instead of halves. This allows the search to adapt dynamically to the size of the array. Beginners can see how sequences from mathematics can directly influence search efficiency.
Program 2: Recursive Fibonacci Search
Fibonacci Search can also be implemented recursively, combining recursion with Fibonacci-based segmenting for a clean approach.
fun fibonacciSearchRecursive(arr: IntArray, target: Int, fibM: Int, fibMm1: Int, fibMm2: Int, offset: Int): Int {
if (fibM <= 1) return if (fibMm1 == 1 && offset + 1 < arr.size && arr[offset + 1] == target) offset + 1 else -1
val i = minOf(offset + fibMm2, arr.size - 1)
return when {
arr[i] < target -> fibonacciSearchRecursive(arr, target, fibMm1, fibMm2, fibMm1 - fibMm2, i)
arr[i] > target -> fibonacciSearchRecursive(arr, target, fibMm2, fibMm1 - fibMm2, fibMm2 - (fibMm1 - fibMm2), offset)
else -> i
}
}
fun main() {
val numbers = intArrayOf(2, 4, 6, 8, 10, 12)
val target = 8
var fibMm2 = 0
var fibMm1 = 1
var fibM = fibMm1 + fibMm2
while (fibM < numbers.size) {
fibMm2 = fibMm1
fibMm1 = fibM
fibM = fibMm1 + fibMm2
}
println("Array: ${numbers.joinToString()}")
val index = fibonacciSearchRecursive(numbers, target, fibM, fibMm1, fibMm2, -1)
if (index != -1) println("Element $target found at index $index")
else println("Element $target not found")
}The recursive approach breaks the problem down into smaller segments until the target is found. Beginners can use this to understand how recursion can simplify complex algorithms.
Program 3: Fibonacci Search on Kotlin List
Fibonacci Search can also be applied to Kotlin List<Int> for more modern applications.
fun fibonacciSearchList(list: List<Int>, target: Int): Int {
val n = list.size
var fibMm2 = 0
var fibMm1 = 1
var fibM = fibMm2 + fibMm1
while (fibM < n) {
fibMm2 = fibMm1
fibMm1 = fibM
fibM = fibMm1 + fibMm2
}
var offset = -1
while (fibM > 1) {
val i = minOf(offset + fibMm2, n - 1)
when {
list[i] < target -> {
fibM = fibMm1
fibMm1 = fibMm2
fibMm2 = fibM - fibMm1
offset = i
}
list[i] > target -> {
fibM = fibMm2
fibMm1 -= fibMm2
fibMm2 = fibM - fibMm1
}
else -> return i
}
}
return if (fibMm1 == 1 && offset + 1 < n && list[offset + 1] == target) offset + 1 else -1
}
fun main() {
val numbers = listOf(1, 3, 5, 7, 9, 11)
val target = 7
println("List: $numbers")
val index = fibonacciSearchList(numbers, target)
if (index != -1) println("Element $target found at index $index")
else println("Element $target not found")
}This example shows how the algorithm adapts to Kotlin collections beyond arrays, maintaining flexibility in practical programming.
Program 4: Fibonacci Search with Duplicates
When a dataset contains duplicate elements, Fibonacci Search can be adjusted to find the first occurrence of a target.
fun fibonacciSearch(arr: IntArray, target: Int): Int {
val n = arr.size
var fibMm2 = 0 // (m-2)'th Fibonacci number
var fibMm1 = 1 // (m-1)'th Fibonacci number
var fibM = fibMm2 + fibMm1 // m'th Fibonacci number
while (fibM < n) {
fibMm2 = fibMm1
fibMm1 = fibM
fibM = fibMm1 + fibMm2
}
var offset = -1
while (fibM > 1) {
val i = minOf(offset + fibMm2, n - 1)
when {
arr[i] < target -> {
fibM = fibMm1
fibMm1 = fibMm2
fibMm2 = fibM - fibMm1
offset = i
}
arr[i] > target -> {
fibM = fibMm2
fibMm1 -= fibMm2
fibMm2 = fibM - fibMm1
}
else -> return i
}
}
return if (fibMm1 == 1 && offset + 1 < n && arr[offset + 1] == target) offset + 1 else -1
}
fun fibonacciSearchFirst(arr: IntArray, target: Int): Int {
var index = fibonacciSearch(arr, target)
while (index > 0 && arr[index - 1] == target) index--
return index
}
fun main() {
val numbers = intArrayOf(5, 10, 10, 15, 20)
val target = 10
println("Array: ${numbers.joinToString()}")
val index = fibonacciSearchFirst(numbers, target)
if (index != -1) println("First occurrence of $target is at index $index")
else println("$target not found")
}This shows beginners how to modify search algorithms for specific requirements, such as handling duplicates in real-world datasets.
Frequently Asked Questions (FAQ)
Here are some common questions about Fibonacci Search in Kotlin.
Q1: What is Fibonacci Search?
Fibonacci Search is a search algorithm that uses Fibonacci numbers to divide a sorted array into segments for efficient searching.
Q2: When should I use Fibonacci Search?
It is best for large, sorted datasets where Fibonacci segmentation may reduce comparisons compared to Binary Search.
Q3: Can it work with Kotlin lists?
Yes, Fibonacci Search can be applied to both arrays and Kotlin lists.
Q4: What is the time complexity?
The time complexity is O(log n), similar to Binary Search, but it uses Fibonacci numbers for division.
Q5: How is it different from Binary Search?
Binary Search splits the array into halves, while Fibonacci Search splits it according to Fibonacci numbers, which can be more flexible for certain datasets.
Conclusion
Fibonacci Search is an efficient and interesting algorithm for searching sorted datasets. In Kotlin, it can be implemented iteratively or recursively and works with arrays and lists. For beginners, it provides a way to explore mathematical sequences in algorithms, understand divide-and-conquer strategies, and handle special cases like duplicates. Practicing Fibonacci Search strengthens problem-solving skills and enhances understanding of search optimization techniques in programming.
