Fibonacci Search Algorithm Code Implementations
Complete Fibonacci Search Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Fibonacci Search Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// Fibonacci Search Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
class FibonacciSearch {
public:
static int fibonacciSearch(const std::vector<int>& arr, int target) {
int n = arr.size();
if (n == 0) return -1;
// Initialize Fibonacci numbers
int fib2 = 0; // (k-2)th Fibonacci number
int fib1 = 1; // (k-1)th Fibonacci number
int fib = fib1 + fib2; // kth Fibonacci number
// Find the smallest Fibonacci number greater than or equal to n
while (fib < n) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
// Initialize the offset
int offset = -1;
// While there are elements to be inspected
while (fib > 1) {
// Check if fib2 is a valid index
int i = std::min(offset + fib2, n - 1);
// If target is greater than the value at index i, cut the subarray from offset to i
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
}
// If target is less than the value at index i, cut the subarray after i+1
else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
}
// Element found
else {
return i;
}
}
// Compare the last element with target
if (fib1 && offset < n - 1 && arr[offset + 1] == target) {
return offset + 1;
}
return -1;
}
// Generate Fibonacci numbers up to n
static std::vector<int> generateFibonacci(int n) {
std::vector<int> fib = {0, 1};
while (fib.back() < n) {
fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
}
return fib;
}
// Fibonacci Search with precomputed Fibonacci numbers
static int fibonacciSearchOptimized(const std::vector<int>& arr, int target) {
int n = arr.size();
if (n == 0) return -1;
std::vector<int> fib = generateFibonacci(n);
int fib2 = fib[fib.size() - 3];
int fib1 = fib[fib.size() - 2];
int fib_k = fib[fib.size() - 1];
int offset = -1;
while (fib_k > 1) {
int i = std::min(offset + fib2, n - 1);
if (arr[i] < target) {
fib_k = fib1;
fib1 = fib2;
fib2 = fib_k - fib1;
offset = i;
} else if (arr[i] > target) {
fib_k = fib2;
fib1 = fib1 - fib2;
fib2 = fib_k - fib1;
} else {
return i;
}
}
if (fib1 && offset < n - 1 && arr[offset + 1] == target) {
return offset + 1;
}
return -1;
}
};JAVA Implementation
// Fibonacci Search Implementation in Java
public class FibonacciSearch {
public static int fibonacciSearch(int[] arr, int target) {
int n = arr.length;
if (n == 0) return -1;
// Initialize Fibonacci numbers
int fib2 = 0; // (k-2)th Fibonacci number
int fib1 = 1; // (k-1)th Fibonacci number
int fib = fib1 + fib2; // kth Fibonacci number
// Find the smallest Fibonacci number greater than or equal to n
while (fib < n) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
// Initialize the offset
int offset = -1;
// While there are elements to be inspected
while (fib > 1) {
// Check if fib2 is a valid index
int i = Math.min(offset + fib2, n - 1);
// If target is greater than the value at index i, cut the subarray from offset to i
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
}
// If target is less than the value at index i, cut the subarray after i+1
else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
}
// Element found
else {
return i;
}
}
// Compare the last element with target
if (fib1 != 0 && offset < n - 1 && arr[offset + 1] == target) {
return offset + 1;
}
return -1;
}
// Generate Fibonacci numbers up to n
public static int[] generateFibonacci(int n) {
java.util.List<Integer> fib = new java.util.ArrayList<>();
fib.add(0);
fib.add(1);
while (fib.get(fib.size() - 1) < n) {
fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
}
return fib.stream().mapToInt(Integer::intValue).toArray();
}
// Fibonacci Search with precomputed Fibonacci numbers
public static int fibonacciSearchOptimized(int[] arr, int target) {
int n = arr.length;
if (n == 0) return -1;
int[] fib = generateFibonacci(n);
int fib2 = fib[fib.length - 3];
int fib1 = fib[fib.length - 2];
int fib_k = fib[fib.length - 1];
int offset = -1;
while (fib_k > 1) {
int i = Math.min(offset + fib2, n - 1);
if (arr[i] < target) {
fib_k = fib1;
fib1 = fib2;
fib2 = fib_k - fib1;
offset = i;
} else if (arr[i] > target) {
fib_k = fib2;
fib1 = fib1 - fib2;
fib2 = fib_k - fib1;
} else {
return i;
}
}
if (fib1 != 0 && offset < n - 1 && arr[offset + 1] == target) {
return offset + 1;
}
return -1;
}
}JAVASCRIPT Implementation
// Fibonacci Search Implementation in JavaScript
function fibonacciSearch(arr, target) {
const n = arr.length;
if (n === 0) return -1;
// Initialize Fibonacci numbers
let fib2 = 0; // (k-2)th Fibonacci number
let fib1 = 1; // (k-1)th Fibonacci number
let fib = fib1 + fib2; // kth Fibonacci number
// Find the smallest Fibonacci number greater than or equal to n
while (fib < n) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
// Initialize the offset
let offset = -1;
// While there are elements to be inspected
while (fib > 1) {
// Check if fib2 is a valid index
const i = Math.min(offset + fib2, n - 1);
// If target is greater than the value at index i, cut the subarray from offset to i
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
}
// If target is less than the value at index i, cut the subarray after i+1
else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
}
// Element found
else {
return i;
}
}
// Compare the last element with target
if (fib1 && offset < n - 1 && arr[offset + 1] === target) {
return offset + 1;
}
return -1;
}
// Generate Fibonacci numbers up to n
function generateFibonacci(n) {
const fib = [0, 1];
while (fib[fib.length - 1] < n) {
fib.push(fib[fib.length - 1] + fib[fib.length - 2]);
}
return fib;
}
// Fibonacci Search with precomputed Fibonacci numbers
function fibonacciSearchOptimized(arr, target) {
const n = arr.length;
if (n === 0) return -1;
const fib = generateFibonacci(n);
let fib2 = fib[fib.length - 3];
let fib1 = fib[fib.length - 2];
let fib_k = fib[fib.length - 1];
let offset = -1;
while (fib_k > 1) {
const i = Math.min(offset + fib2, n - 1);
if (arr[i] < target) {
fib_k = fib1;
fib1 = fib2;
fib2 = fib_k - fib1;
offset = i;
} else if (arr[i] > target) {
fib_k = fib2;
fib1 = fib1 - fib2;
fib2 = fib_k - fib1;
} else {
return i;
}
}
if (fib1 && offset < n - 1 && arr[offset + 1] === target) {
return offset + 1;
}
return -1;
}PYTHON Implementation
# Fibonacci Search Implementation in Python
def fibonacci_search(arr, target):
n = len(arr)
if n == 0:
return -1
# Initialize Fibonacci numbers
fib2 = 0 # (k-2)th Fibonacci number
fib1 = 1 # (k-1)th Fibonacci number
fib = fib1 + fib2 # kth Fibonacci number
# Find the smallest Fibonacci number greater than or equal to n
while fib < n:
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
# Initialize the offset
offset = -1
# While there are elements to be inspected
while fib > 1:
# Check if fib2 is a valid index
i = min(offset + fib2, n - 1)
# If target is greater than the value at index i, cut the subarray from offset to i
if arr[i] < target:
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = i
# If target is less than the value at index i, cut the subarray after i+1
elif arr[i] > target:
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
# Element found
else:
return i
# Compare the last element with target
if fib1 and offset < n - 1 and arr[offset + 1] == target:
return offset + 1
return -1
# Generate Fibonacci numbers up to n
def generate_fibonacci(n):
fib = [0, 1]
while fib[-1] < n:
fib.append(fib[-1] + fib[-2])
return fib
# Fibonacci Search with precomputed Fibonacci numbers
def fibonacci_search_optimized(arr, target):
n = len(arr)
if n == 0:
return -1
fib = generate_fibonacci(n)
fib2 = fib[-3]
fib1 = fib[-2]
fib_k = fib[-1]
offset = -1
while fib_k > 1:
i = min(offset + fib2, n - 1)
if arr[i] < target:
fib_k = fib1
fib1 = fib2
fib2 = fib_k - fib1
offset = i
elif arr[i] > target:
fib_k = fib2
fib1 = fib1 - fib2
fib2 = fib_k - fib1
else:
return i
if fib1 and offset < n - 1 and arr[offset + 1] == target:
return offset + 1
return -1