Поиск ФибоначчиFibonacci Search

Выбирается наименьшее число Фибоначчи F(m), не меньшее размера массива n. Вместо деления диапазона пополам, точка проверки берётся на расстоянии F(m-2) от текущего смещения offset — то есть в пропорции, заданной соседними числами Фибоначчи, а не 50/50. Если a[i] < x, диапазон сдвигается вправо, и "текущее число Фибоначчи" уменьшается на два индекса вниз по последовательности (F(m) → F(m-1)); если a[i] > x — диапазон сокращается слева, и число Фибоначчи падает на один индекс (F(m) → F(m-2)). В любом случае размер оставшегося диапазона — это снова число Фибоначчи, что позволяет продолжать без явного деления на всех последующих шагах.The smallest Fibonacci number F(m) not less than the array size n is chosen. Instead of halving the range, the check point is taken at distance F(m-2) from the current offset — a proportion set by neighboring Fibonacci numbers, not 50/50. If a[i] < x, the range shifts right, and the "current Fibonacci number" drops two indices down the sequence (F(m) → F(m-1)); if a[i] > x, the range shrinks on the left, and the Fibonacci number drops by one index (F(m) → F(m-2)). Either way, the remaining range's size is again a Fibonacci number, allowing the process to continue with no explicit division at any subsequent step.

int fibonacci_search(const std::vector<int>& a, int x) {
    int n = (int)a.size();
    int fib2 = 0, fib1 = 1, fibM = fib1 + fib2;  // найти наименьшее F(m) >= n// find the smallest F(m) >= n
    while (fibM < n) { fib2 = fib1; fib1 = fibM; fibM = fib1 + fib2; }

    int offset = -1;
    while (fibM > 1) {
        int i = std::min(offset + fib2, n - 1);
        if (a[i] < x) {                       // сдвиг вправо — только сложение/вычитание// shift right — only addition/subtraction
            fibM = fib1; fib1 = fib2; fib2 = fibM - fib1;
            offset = i;
        } else if (a[i] > x) {                // сужение слева// narrow on the left
            fibM = fib2; fib1 = fib1 - fib2; fib2 = fibM - fib1;
        } else {
            return i;
        }
    }
    if (fib1 && offset + 1 < n && a[offset + 1] == x) return offset + 1;
    return -1;
}

Жёлтая полоса — текущая точка проверки, определяемая числами Фибоначчи (показаны в логе), а не серединой диапазона. Обратите внимание, что деление пополам никогда не используется — только сложение/вычитание заранее известных чисел.The yellow bar is the current check point, set by Fibonacci numbers (shown in the log), not the range's midpoint. Notice that halving is never used — only addition/subtraction of pre-known numbers.

Числа Фибоначчи растут экспоненциально с основанием φ = (1+√5)/2 ≈ 1.618 (золотое сечение) — F(m) ~ φ^m/√5. Число шагов, необходимое для сведения диапазона размера n к константе, пропорционально log_φ(n), что по свойствам логарифмов равно log(n)/log(φ) — та же асимптотика O(log n), что и у бинарного поиска, с чуть большей константой (1/log₂(φ) ≈ 1.44 против 1 у честного деления пополам). Небольшое отставание в константе — это и есть цена отказа от деления в пользу только сложения/вычитания.Fibonacci numbers grow exponentially with base φ = (1+√5)/2 ≈ 1.618 (the golden ratio) — F(m) ~ φ^m/√5. The number of steps needed to reduce a range of size n to a constant is proportional to log_φ(n), which by logarithm properties equals log(n)/log(φ) — the same O(log n) asymptotics as binary search, with a slightly larger constant (1/log₂(φ) ≈ 1.44 versus 1 for honest halving). This small constant-factor penalty is exactly the price of trading division for addition/subtraction only.