AntInLoop

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