Searching efficiently is a fundamental skill in programming, especially when working with large datasets. One interesting and effective algorithm is Fibonacci Search, which is designed for sorted arrays. Unlike Binary Search, which splits arrays in halves, Fibonacci Search uses Fibonacci numbers to divide the array into sections, making it particularly useful when dealing with large, sorted datasets or when memory access is costly. This method reduces the number of comparisons needed to locate an element.
with hands-on learning.
get the skills and confidence to land your next move.
Fibonacci Search is widely applied in areas like database indexing, file searching, and memory-efficient searching, especially when sequential access is slower than random access. For beginners, it provides an excellent opportunity to learn how mathematical sequences, like the Fibonacci numbers, can optimize algorithms and improve performance.
Program 1: Basic Fibonacci Search for Integers
This program demonstrates a classic Fibonacci Search using a simple sorted integer array. It finds a target number by calculating Fibonacci numbers to determine potential positions.
Module Module1
Function FibonacciSearch(arr() As Integer, target As Integer) As Integer
Dim n As Integer = arr.Length
Dim fibMMm2 As Integer = 0
Dim fibMMm1 As Integer = 1
Dim fibM As Integer = fibMMm2 + fibMMm1
While fibM < n
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
End While
Dim offset As Integer = -1
While fibM > 1
Dim i As Integer = Math.Min(offset + fibMMm2, n - 1)
If arr(i) < target Then
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
ElseIf arr(i) > target Then
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
Else
Return i
End If
End While
If fibMMm1 = 1 AndAlso offset + 1 < n AndAlso arr(offset + 1) = target Then
Return offset + 1
End If
Return -1
End Function
Sub Main()
Dim data() As Integer = {1, 3, 5, 7, 9, 11, 13, 15}
Dim target As Integer = 9
Dim result As Integer = FibonacciSearch(data, target)
If result <> -1 Then
Console.WriteLine("Element found at position: " & result)
Else
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleThe program calculates Fibonacci numbers to determine positions in the array to compare against the target. This allows it to efficiently reduce the search range. Beginners can see how Fibonacci numbers act as dynamic pivots in searching.
Program 2: Fibonacci Search with Negative Numbers
This program handles arrays containing negative numbers, showing the algorithm works for all integers in a sorted array.
Module Module1
Function FibonacciSearch(arr() As Integer, target As Integer) As Integer
Dim n As Integer = arr.Length
Dim fibMMm2 As Integer = 0
Dim fibMMm1 As Integer = 1
Dim fibM As Integer = fibMMm2 + fibMMm1
While fibM < n
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
End While
Dim offset As Integer = -1
While fibM > 1
Dim i As Integer = Math.Min(offset + fibMMm2, n - 1)
If arr(i) < target Then
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
ElseIf arr(i) > target Then
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
Else
Return i
End If
End While
If fibMMm1 = 1 AndAlso offset + 1 < n AndAlso arr(offset + 1) = target Then
Return offset + 1
End If
Return -1
End Function
Sub Main()
Dim data() As Integer = {-20, -10, 0, 5, 10, 15, 20}
Dim target As Integer = -10
Dim result As Integer = FibonacciSearch(data, target)
If result <> -1 Then
Console.WriteLine("Element found at position: " & result)
Else
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleFibonacci Search works with negative values as long as the array is sorted. This demonstrates its flexibility and robustness for beginners learning about array-based search algorithms.
Program 3: Fibonacci Search for Floating-Point Numbers
This program extends Fibonacci Search to decimal numbers, showing the algorithm’s versatility.
Module Module1
Function FibonacciSearch(arr() As Double, target As Double) As Integer
Dim n As Integer = arr.Length
Dim fibMMm2 As Integer = 0
Dim fibMMm1 As Integer = 1
Dim fibM As Integer = fibMMm2 + fibMMm1
While fibM < n
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
End While
Dim offset As Integer = -1
While fibM > 1
Dim i As Integer = Math.Min(offset + fibMMm2, n - 1)
If arr(i) < target Then
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
ElseIf arr(i) > target Then
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
Else
Return i
End If
End While
If fibMMm1 = 1 AndAlso offset + 1 < n AndAlso arr(offset + 1) = target Then
Return offset + 1
End If
Return -1
End Function
Sub Main()
Dim data() As Double = {0.5, 1.0, 1.5, 2.0, 2.5, 3.0}
Dim target As Double = 2.5
Dim result As Integer = FibonacciSearch(data, target)
If result <> -1 Then
Console.WriteLine("Element found at position: " & result)
Else
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleThe same algorithm applies to floating-point numbers, making it a versatile choice for different types of numeric datasets. Beginners can practice with integers, negatives, and decimals using the same logic.
Program 4: Interactive Fibonacci Search
This program allows the user to enter their own sorted array and target value, demonstrating practical use.
Module Module1
Function FibonacciSearch(arr() As Integer, target As Integer) As Integer
Dim n As Integer = arr.Length
Dim fibMMm2 As Integer = 0
Dim fibMMm1 As Integer = 1
Dim fibM As Integer = fibMMm2 + fibMMm1
While fibM < n
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
End While
Dim offset As Integer = -1
While fibM > 1
Dim i As Integer = Math.Min(offset + fibMMm2, n - 1)
If arr(i) < target Then
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
ElseIf arr(i) > target Then
fibM = fibMMm2
fibMMm1 -= fibMMm2
fibMMm2 = fibM - fibMMm1
Else
Return i
End If
End While
If fibMMm1 = 1 AndAlso offset + 1 < n AndAlso arr(offset + 1) = target Then
Return offset + 1
End If
Return -1
End Function
Sub Main()
Console.WriteLine("Enter sorted numbers separated by space:")
Dim input As String = Console.ReadLine()
Dim data() As Integer = Array.ConvertAll(input.Split(" "c), Function(s) Int32.Parse(s))
Console.WriteLine("Enter number to search:")
Dim target As Integer = Int32.Parse(Console.ReadLine())
Dim result As Integer = FibonacciSearch(data, target)
If result <> -1 Then
Console.WriteLine("Element found at position: " & result)
Else
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleThis interactive version lets beginners experiment with different datasets, showing the real-world application of Fibonacci Search.
Program 5: Recursive Fibonacci Search
This version demonstrates a recursive approach, offering an alternative perspective on the algorithm.
Module Module1
Function FibonacciSearchRecursive(arr() As Integer, target As Integer, fibM As Integer, fibMMm1 As Integer, fibMMm2 As Integer, offset As Integer) As Integer
If fibM <= 1 Then
If offset + 1 < arr.Length AndAlso arr(offset + 1) = target Then Return offset + 1
Return -1
End If
Dim i As Integer = Math.Min(offset + fibMMm2, arr.Length - 1)
If arr(i) < target Then
Return FibonacciSearchRecursive(arr, target, fibMMm1, fibMMm2, fibMMm1 - fibMMm2, i)
ElseIf arr(i) > target Then
Return FibonacciSearchRecursive(arr, target, fibMMm2, fibMMm1 - fibMMm2, fibMMm2 - (fibMMm1 - fibMMm2), offset)
Else
Return i
End If
End Function
Sub Main()
Dim data() As Integer = {1, 4, 7, 10, 13, 16}
Dim target As Integer = 10
' Calculate initial Fibonacci numbers
Dim fibMMm2 As Integer = 0
Dim fibMMm1 As Integer = 1
Dim fibM As Integer = fibMMm2 + fibMMm1
While fibM < data.Length
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
End While
Dim result As Integer = FibonacciSearchRecursive(data, target, fibM, fibMMm1, fibMMm2, -1)
If result <> -1 Then
Console.WriteLine("Element found at position: " & result)
Else
Console.WriteLine("Element not found in the array.")
End If
Console.ReadLine()
End Sub
End ModuleRecursion offers a clear, step-by-step view of how Fibonacci Search reduces the search space. Beginners can compare this with iterative methods to understand different programming approaches.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Fibonacci Search:
Q1: What is the main advantage of Fibonacci Search?
It reduces the number of comparisons by using Fibonacci numbers as pivot points, making it efficient for large sorted arrays.
Q2: Can Fibonacci Search handle negative numbers or decimals?
Yes, as long as the array is sorted, it works for all numeric types.
Q3: How does Fibonacci Search differ from Binary Search?
Binary Search splits the array into halves, while Fibonacci Search uses Fibonacci numbers to determine split points, which can sometimes reduce comparisons.
Q4: Is Fibonacci Search faster than Binary Search?
It depends on the dataset. Fibonacci Search can be slightly more efficient for sequentially accessed arrays.
Q5: What is required for Fibonacci Search to work?
The array must be sorted, and the algorithm assumes that element access is possible in constant time.
Conclusion
Fibonacci Search is a mathematically inspired search algorithm that efficiently locates elements in sorted arrays. By exploring integer, negative, decimal, interactive, and recursive versions, beginners can understand its versatility and efficiency. Practicing Fibonacci Search in VB .NET strengthens both algorithmic thinking and practical programming skills, making it a valuable addition to any beginner’s toolkit.
