Fibonacci Search is an efficient searching algorithm that uses the Fibonacci sequence to locate an element in a sorted array. Unlike Binary Search, which divides the array in half each time, Fibonacci Search divides the array based on Fibonacci numbers, which allows it to reduce the search range in a slightly different pattern. This approach can be particularly useful for systems where computing the middle index is expensive, as it relies on addition and subtraction rather than division.
For beginners learning R programming, Fibonacci Search is a great way to explore how mathematical sequences, like Fibonacci numbers, can be applied to real-world algorithm design. It is commonly used in large sorted datasets such as stock prices, sorted sensor data, or numeric records where efficient searching is critical. Practicing this algorithm helps learners understand iteration, array indexing, and the logic of dividing problems into smaller parts efficiently.
Program 1: Basic Fibonacci Search using loops
This program demonstrates how to implement Fibonacci Search in R using a loop to find an element in a sorted array.
fibonacci_search <- function(arr, target) {
n <- length(arr)
fibM_minus_2 <- 0
fibM_minus_1 <- 1
fibM <- fibM_minus_1 + fibM_minus_2
while (fibM < n) {
fibM_minus_2 <- fibM_minus_1
fibM_minus_1 <- fibM
fibM <- fibM_minus_1 + fibM_minus_2
}
offset <- 0
while (fibM > 1) {
i <- min(offset + fibM_minus_2, n)
if (arr[i] < target) {
fibM <- fibM_minus_1
fibM_minus_1 <- fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
offset <- i
} else if (arr[i] > target) {
fibM <- fibM_minus_2
fibM_minus_1 <- fibM_minus_1 - fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
} else {
return(i)
}
}
if (fibM_minus_1 == 1 && offset + 1 <= n && arr[offset + 1] == target)
return(offset + 1)
-1
}
data <- c(1, 3, 5, 7, 9, 11, 13)
target <- 5
print(fibonacci_search(data, target))This program works by generating the smallest Fibonacci number greater than or equal to the array length. It then uses the sequence to narrow down the search range. Beginners can understand it as a clever way to “jump” across the array in Fibonacci-sized steps instead of halving it like Binary Search.
Program 2: Fibonacci Search using recursion
This version uses recursion to implement the search logic, making it easier to see the step-by-step process.
fibonacci_search_rec <- function(arr, target, offset = 0, fibM_minus_2 = 0, fibM_minus_1 = 1, fibM = 1) {
n <- length(arr)
if (fibM < n) {
return(fibonacci_search_rec(arr, target, offset, fibM_minus_1, fibM, fibM_minus_1 + fibM))
}
while (fibM > 1) {
i <- min(offset + fibM_minus_2, n)
if (arr[i] < target) {
offset <- i
temp <- fibM_minus_1
fibM_minus_1 <- fibM_minus_2
fibM_minus_2 <- fibM - temp
fibM <- temp
} else if (arr[i] > target) {
temp <- fibM_minus_1
fibM_minus_1 <- fibM_minus_2
fibM_minus_2 <- fibM - temp
fibM <- fibM_minus_2
} else {
return(i)
}
}
if (fibM_minus_1 == 1 && offset + 1 <= n && arr[offset + 1] == target) {
return(offset + 1)
}
return(-1)
}
data <- c(2, 4, 6, 8, 10, 12)
target <- 12
print(fibonacci_search_rec(data, target))Recursion allows beginners to observe the algorithm’s decision-making process at each step and is a useful way to practice recursive thinking in R.
Program 3: Fibonacci Search with negative numbers
The algorithm works with negative numbers as long as the array is sorted.
fibonacci_search <- function(arr, target) {
n <- length(arr)
fibM_minus_2 <- 0
fibM_minus_1 <- 1
fibM <- fibM_minus_1 + fibM_minus_2
while (fibM < n) {
fibM_minus_2 <- fibM_minus_1
fibM_minus_1 <- fibM
fibM <- fibM_minus_1 + fibM_minus_2
}
offset <- 0
while (fibM > 1) {
i <- min(offset + fibM_minus_2, n)
if (arr[i] < target) {
fibM <- fibM_minus_1
fibM_minus_1 <- fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
offset <- i
} else if (arr[i] > target) {
fibM <- fibM_minus_2
fibM_minus_1 <- fibM_minus_1 - fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
} else {
return(i)
}
}
if (fibM_minus_1 == 1 && offset + 1 <= n && arr[offset + 1] == target)
return(offset + 1)
-1
}
data <- c(-20, -15, -10, -5, 0, 5, 10)
target <- -10
print(fibonacci_search(data, target))This demonstrates that Fibonacci Search is versatile and can be applied to datasets containing negative values, such as temperature readings or financial records.
Program 4: Fibonacci Search with floating-point numbers
Fibonacci Search can also handle arrays containing decimals, which is useful for scientific or financial datasets.
fibonacci_search <- function(arr, target) {
n <- length(arr)
fibM_minus_2 <- 0
fibM_minus_1 <- 1
fibM <- fibM_minus_1 + fibM_minus_2
while (fibM < n) {
fibM_minus_2 <- fibM_minus_1
fibM_minus_1 <- fibM
fibM <- fibM_minus_1 + fibM_minus_2
}
offset <- 0
while (fibM > 1) {
i <- min(offset + fibM_minus_2, n)
if (arr[i] < target) {
fibM <- fibM_minus_1
fibM_minus_1 <- fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
offset <- i
} else if (arr[i] > target) {
fibM <- fibM_minus_2
fibM_minus_1 <- fibM_minus_1 - fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
} else {
return(i)
}
}
if (fibM_minus_1 == 1 && offset + 1 <= n && arr[offset + 1] == target)
return(offset + 1)
-1
}
data <- c(0.1, 1.5, 2.3, 3.7, 4.8)
target <- 3.7
print(fibonacci_search(data, target))Beginners can see that the search logic works for both integers and floating-point numbers without any change in the algorithm.
Program 5: Fibonacci Search for first occurrence of duplicates
This program modifies the search to return the first occurrence of a duplicate element.
fibonacci_search <- function(arr, target) {
n <- length(arr)
fibM_minus_2 <- 0
fibM_minus_1 <- 1
fibM <- fibM_minus_1 + fibM_minus_2
while (fibM < n) {
fibM_minus_2 <- fibM_minus_1
fibM_minus_1 <- fibM
fibM <- fibM_minus_1 + fibM_minus_2
}
offset <- 0
while (fibM > 1) {
i <- min(offset + fibM_minus_2, n)
if (arr[i] < target) {
fibM <- fibM_minus_1
fibM_minus_1 <- fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
offset <- i
} else if (arr[i] > target) {
fibM <- fibM_minus_2
fibM_minus_1 <- fibM_minus_1 - fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
} else {
return(i)
}
}
if (fibM_minus_1 == 1 && offset + 1 <= n && arr[offset + 1] == target)
return(offset + 1)
-1
}
fibonacci_search_first <- function(arr, target) {
pos <- fibonacci_search(arr, target)
if (pos == -1) return(-1)
while (pos > 1 && arr[pos - 1] == target) {
pos <- pos - 1
}
return(pos)
}
data <- c(1, 2, 2, 2, 3, 4)
target <- 2
print(fibonacci_search_first(data, target))This teaches beginners that small modifications can adapt the algorithm for real-world situations where duplicates exist.
Program 6: Input validation for Fibonacci Search
Adding validation ensures the array is sorted in ascending order, which prevents unexpected results.
fibonacci_search <- function(arr, target) {
n <- length(arr)
fibM_minus_2 <- 0
fibM_minus_1 <- 1
fibM <- fibM_minus_1 + fibM_minus_2
while (fibM < n) {
fibM_minus_2 <- fibM_minus_1
fibM_minus_1 <- fibM
fibM <- fibM_minus_1 + fibM_minus_2
}
offset <- 0
while (fibM > 1) {
i <- min(offset + fibM_minus_2, n)
if (arr[i] < target) {
fibM <- fibM_minus_1
fibM_minus_1 <- fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
offset <- i
} else if (arr[i] > target) {
fibM <- fibM_minus_2
fibM_minus_1 <- fibM_minus_1 - fibM_minus_2
fibM_minus_2 <- fibM - fibM_minus_1
} else {
return(i)
}
}
if (fibM_minus_1 == 1 && offset + 1 <= n && arr[offset + 1] == target)
return(offset + 1)
-1
}
fibonacci_search_safe <- function(arr, target) {
if (!all(diff(arr) >= 0)) stop("Array must be sorted in ascending order")
fibonacci_search(arr, target)
}
data <- c(1, 3, 5, 7)
target <- 5
print(fibonacci_search_safe(data, target))Input validation teaches good programming practices, especially for beginners implementing search algorithms.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Fibonacci Search in R.
Q1. Can Fibonacci Search work on unsorted arrays?
No, it requires a sorted array to locate the target correctly.
Q2. How is Fibonacci Search different from Binary Search?
It uses Fibonacci numbers to determine the range for the next comparison instead of splitting the array in half.
Q3. Can it handle negative or decimal numbers?
Yes, as long as the array is sorted, Fibonacci Search works with any numeric values.
Q4. Can it find the first occurrence among duplicates?
Yes, with minor modifications, it can locate the first occurrence in arrays with duplicate values.
Conclusion
Fibonacci Search is a clever algorithm that efficiently locates elements in sorted arrays by leveraging the Fibonacci sequence. Beginners can explore both iterative and recursive implementations, handle negative and floating-point numbers, and adapt the algorithm for duplicates.
Practicing Fibonacci Search in R helps strengthen understanding of array indexing, recursion, iteration, and algorithmic thinking. It’s a valuable skill for anyone working with sorted datasets and builds a strong foundation for more advanced search techniques.
