Fibonacci Search Technique

The Fibonacci search technique is a divide-and-conquer search algorithm that applies the principles of Fibonacci numbers to narrow down targets within a sorted array. Unlike standard binary search, which strictly bisects the search space at each iteration using bitwise shifts or arithmetic division, Fibonacci search utilizes asymmetric partitioning based on the golden ratio approximation embedded within the Fibonacci sequence. This eliminates division operations, making it optimal for specialized low-level architectures, magnetic disk seeks, and non-uniform memory access (NUMA) systems where division carries a high CPU cycle penalty.

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

// Finds the smallest Fibonacci number >= n
size_t get_fibonacci_m(size_t n) {
    size_t fibMMm2 = 0; // (m-2)th Fibonacci
    size_t fibMMm1 = 1; // (m-1)th Fibonacci
    size_t fibM = fibMMm2 + fibMMm1; // mth Fibonacci

    while (fibM < n) {
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm2 + fibMMm1;
    }
    return fibM;
}

int64_t fibonacci_search(const int32_t *arr, size_t n, int32_t x) {
    size_t fibMMm2 = 0;
    size_t fibMMm1 = 1;
    size_t fibM = fibMMm2 + fibMMm1;

    while (fibM < n) {
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm2 + fibMMm1;
    }

    int64_t offset = -1;

    while (fibM > 1) {
        size_t i = (offset + fibMMm2 < n - 1) ? (offset + fibMMm2) : (n - 1);

        if (arr[i] < x) {
            fibM = fibMMm1;
            fibMMm1 = fibMMm2;
            fibMMm2 = fibM - fibMMm1;
            offset = i;
        } else if (arr[i] > x) {
            fibM = fibMMm2;
            fibMMm1 = fibMMm1 - fibMMm2;
            fibMMm2 = fibM - fibMMm1;
        } else {
            return (int64_t)i;
        }
    }

    if (fibMMm1 && (offset + 1 < n) && arr[offset + 1] == x) {
        return (int64_t)(offset + 1);
    }

    return -1;
}

#assert fibonacci_search((int32_t[]){2, 3, 4, 10, 40}, 5, 10) == 3
#assert fibonacci_search((int32_t[]){5}, 1, 5) == 0
#assert fibonacci_search((int32_t[]){1, 2, 3}, 3, 99) == -1

// Ensure max array size bounds fit within maximum non-overflowing Fibonacci index for 64-bit integers (F(92))
#define MAX_FIB_INDEX 92

void validate_environment(size_t n) {
    if (n > 7540113804746346429ULL) {
        // F(92) boundary reached for 64-bit signed integers
        fprintf(stderr, "Error: Array size exceeds Fibonacci search capacity.n");
    }
}

Mathematical Foundation & Mechanics

Fibonacci search relies on the property that the ratio of consecutive Fibonacci numbers converges to the golden ratio phi = (1 + sqrt(5)) / 2 approx 1.618. Given a sorted array of size n, we select a Fibonacci number F(k) such that F(k) >= n. The search space is split into two segments whose lengths are consecutive Fibonacci numbers F(k-1) and F(k-2). When inspecting the element at index offset + F(k-2), if the target is greater than the current element, the lower bound shifts past the index, and the remaining search space reduces to size F(k-1). If smaller, the search space reduces to F(k-2).

Architectural Trade-offs vs Binary Search

While binary search achieves O(log n) time complexity with uniform bisection, it requires computing midpoints via division or bitwise right-shifts (n / 2). On older or embedded microarchitectures lacking hardware division units, division incurs dozens of CPU cycles. Fibonacci search replaces division and multiplication operations with simple additions and subtractions within the loop. However, its memory access pattern can exhibit lower spatial locality cache performance compared to standard binary search due to asymmetric jumping across the array elements.

Failure Modes & Edge Cases

A primary production failure mode occurs when padding virtual elements beyond the true end of the array (when n + 1 != F(k)). Accessing indices greater than n – 1 requires strict conditional clamping (using n – 1 as the maximum index) to prevent out-of-bounds memory reads. Furthermore, integer overflow must be accounted for if array dimensions approach the limit of 64-bit integer representations of Fibonacci numbers.