When working with sorted arrays, knowing how to search efficiently is an essential skill for programmers. While algorithms like Binary Search and Exponential Search are popular, Fibonacci Search offers an interesting alternative that leverages the Fibonacci sequence to narrow down search ranges. It’s especially useful in situations where the cost of accessing elements increases with their index, or when you want a search method that avoids division operations like Binary Search.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search works by dividing the array into sections whose sizes are consecutive Fibonacci numbers. This helps efficiently locate the target element while maintaining a time complexity similar to Binary Search, which is O(log n). For beginners, implementing Fibonacci Search in GoLang provides an excellent way to understand how sequences, array indexing, and search algorithms come together in practical programming.
Program 1: Basic Fibonacci Search
This program demonstrates the standard Fibonacci Search. It uses the Fibonacci sequence to narrow down the search range and locate the target element in a sorted array.
package main
import "fmt"
func fibonacciSearch(arr []int, target int) int {
n := len(arr)
fib2, fib1 := 0, 1
fib := fib1 + fib2
for fib < n {
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
}
offset := -1
for fib > 1 {
i := min(offset+fib2, n-1)
if arr[i] < target {
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = i
} else if arr[i] > target {
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
} else {
return i
}
}
if fib1 == 1 && offset+1 < n && arr[offset+1] == target {
return offset + 1
}
return -1
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
numbers := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
target := 11
index := fibonacciSearch(numbers, target)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}This program builds a Fibonacci sequence until it exceeds the array length, then uses it to divide the array and find the target element. Beginners can see how the sequence determines the search steps and how offset handling keeps track of array positions.
Program 2: Recursive Fibonacci Search
Fibonacci Search can also be implemented recursively for clarity and elegance. This version breaks down the array according to Fibonacci numbers and searches recursively.
package main
import "fmt"
func fibonacciSearchRecursive(arr []int, target int, fibM, fibMMm1, fibMMm2, offset int) int {
if fibM == 0 {
return -1
}
i := min(offset+fibMMm2, len(arr)-1)
if arr[i] == target {
return i
} else if arr[i] < target {
return fibonacciSearchRecursive(arr, target, fibMMm1, fibMMm2, fibMMm1-fibMMm2, i)
} else {
return fibonacciSearchRecursive(arr, target, fibMMm2, fibMMm1-fibMMm2, fibMMm2-fibMMm1+fibMMm2, offset)
}
}
func main() {
numbers := []int{2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
target := 14
fib2, fib1 := 0, 1
fib := fib1 + fib2
for fib < len(numbers) {
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
}
index := fibonacciSearchRecursive(numbers, target, fib, fib1, fib2, -1)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}The recursive approach shows how each search step reduces the array according to Fibonacci numbers. Beginners can appreciate how recursion naturally handles repeated search steps.
Program 3: Fibonacci Search with Step Printing
Seeing the Fibonacci Search in action can help beginners understand how the algorithm jumps and narrows ranges. This version prints each comparison and array index checked.
package main
import "fmt"
func fibonacciSearchPrint(arr []int, target int) int {
n := len(arr)
fib2, fib1 := 0, 1
fib := fib1 + fib2
for fib < n {
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
}
offset := -1
for fib > 1 {
i := min(offset+fib2, n-1)
fmt.Printf("Checking index %d: %d\n", i, arr[i])
if arr[i] < target {
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = i
} else if arr[i] > target {
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
} else {
return i
}
}
if fib1 == 1 && offset+1 < n && arr[offset+1] == target {
return offset + 1
}
return -1
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
numbers := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
target := 7
index := fibonacciSearchPrint(numbers, target)
if index != -1 {
fmt.Printf("Element %d found at index %d\n", target, index)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}Printing the index being checked helps beginners visualize how the algorithm uses Fibonacci numbers to skip certain sections, making the search efficient.
Program 4: Fibonacci Search Handling Multiple Occurrences
This version adapts Fibonacci Search to locate all instances of a target value in the array.
package main
import "fmt"
func fibonacciSearchAll(arr []int, target int) []int {
n := len(arr)
fib2, fib1 := 0, 1
fib := fib1 + fib2
for fib < n {
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
}
offset := -1
indices := []int{}
for fib > 1 {
i := min(offset+fib2, n-1)
if arr[i] < target {
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = i
} else if arr[i] > target {
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
} else {
// Found target, explore left and right
l, r := i, i
for l >= 0 && arr[l] == target {
indices = append([]int{l}, indices...)
l--
}
for r < n && arr[r] == target {
if r != i {
indices = append(indices, r)
}
r++
}
break
}
}
if fib1 == 1 && offset+1 < n && arr[offset+1] == target {
indices = append(indices, offset+1)
}
return indices
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
numbers := []int{1, 3, 3, 3, 5, 7, 9, 11}
target := 3
indices := fibonacciSearchAll(numbers, target)
if len(indices) > 0 {
fmt.Printf("Element %d found at indices %v\n", target, indices)
} else {
fmt.Printf("Element %d not found in the array\n", target)
}
}This program demonstrates how Fibonacci Search can be extended to handle duplicates, showing beginners the flexibility of the algorithm.
Frequently Asked Questions (FAQ)
Q1: What is Fibonacci Search?
Fibonacci Search is an algorithm that searches a sorted array using Fibonacci numbers to divide the array into sections efficiently.
Q2: When should I use Fibonacci Search?
It is useful for large sorted arrays, especially when accessing elements has varying costs or when division operations are costly.
Q3: How does Fibonacci Search compare to Binary Search?
Both have O(log n) time complexity, but Fibonacci Search uses addition/subtraction instead of division, which can be more efficient in certain scenarios.
Q4: Can Fibonacci Search find multiple occurrences?
Yes, with minor modifications, it can locate all indices of the target element.
Q5: Where is Fibonacci Search used in practice?
It’s used in database indexing, file search, and applications where sequential memory access is more efficient than random access.
Conclusion
Fibonacci Search is a fascinating and efficient search algorithm that combines the elegance of the Fibonacci sequence with the practicality of array search. By learning iterative, recursive, step-printed, and duplicate-handling versions, beginners gain a strong understanding of hybrid search techniques in GoLang.
Practicing with different array sizes, values, and target positions will strengthen your grasp of Fibonacci Search, preparing you to handle both simple and advanced search problems efficiently.
