Реализация алгоритма поиска Фибоначчи в Python | Ежедневный Python # 27

Эта статья представляет собой руководство по реализации алгоритма поиска Фибоначчи в Python и является продолжением Daily Python # 21.

Эта статья - часть задачи Daily Python, которую я взял на себя. Я буду писать короткие статьи о Python ежедневно.

Для этой статьи нет дополнительных требований.

Если вы не читали часть 1 основных алгоритмов поиска, вы можете прочитать ее здесь:

Поиск по Фибоначчи

Поиск по Фибоначчи - это метод, основанный на сравнении, который использует числа Фибоначчи для поиска элемента в отсортированном массиве.

1. Работает для отсортированных массивов
2. Алгоритм разделяй и властвуй.
3. Имеет временную сложность Log n.

Отличия от двоичного поиска:

1. Поиск Фибоначчи делит заданный массив на неравные части
2. Двоичный поиск использует оператор деления для разделения диапазона. Поиск Фибоначчи не использует /, но использует + и -. Оператор деления может быть дорогостоящим для некоторых процессоров.
3. Поиск Фибоначчи исследует относительно близкие элементы на следующих этапах. Поэтому, когда входной массив большой и не помещается в кеш-память ЦП или даже в ОЗУ, поиск по Фибоначчи может быть полезен.

Справочная информация:

Числа Фибоначчи рекурсивно определяются как F (n) = F (n-1) + F (n-2), F (0) = 0, F (1) = 1. Первые несколько чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

Давайте определим функцию для генерации числа Фибоначчи с индексом n.

def FibonacciGenerator(n):
    if n < 1:
        return 0
    elif n == 1:
        return 1
    else:
        return FibonacciGenerator(n - 1) + FibonacciGenerator(n - 2)

Давайте рассмотрим следующий массив и число для поиска

arr = [10, 22, 30, 44, 56, 58, 60, 70, 100, 110, 130] 
x = 60

Теперь давайте определим функцию, которая будет делить список и искать число в соответствии с поиском Фибоначчи.

def FibonacciSearch(arr, x):
    m = 0 
    while FibonacciGenerator(m) < len(arr): # 
        m = m + 1 
    offset = -1    
    while (FibonacciGenerator(m) > 1):
        i = min( offset + FibonacciGenerator(m - 2) , len(arr) - 1)
        print('Current Element : ',arr[i])
        if (x > arr[i]):
            m = m - 1
            offset = i
        elif (x < arr[i]):
            m = m - 2
        else:
            return i        
    if(FibonacciGenerator(m - 1) and arr[offset + 1] == x):
        return offset + 1
    return -1
print('Number found at index : ',FibonacciSearch(arr, x))

Надеюсь, эта статья была полезной, оставьте несколько аплодисментов, если она вам понравилась.

Следите за ежедневным вызовом Python здесь: