Алгоритмы. Поиск Фибоначчи. Реализация на Python и Java.

В этой лекции будет рассмотрен интересный алгоритм поиска. Это поиск Фибоначчи. Идея этого поиска лежит в использовании для поиска последовательности Фибоначчи. Этот подход стоит использовать в системах где операция деления не поддерживается или выполняется медленно. В лекции будет рассмотрена реализация этого алгоритма на Python и Java.

[igoryegorov]

Оставлю комментарий в поддержку и продвижение канала. Благодарю за доступное и подробное изложение.

[KALMAPUK]

спасибо, хорошо рассказал, реализовал, проверил работает.

[dima_kv]

А в чем может быть проблема с компьютерным делением? Деление бинарного отрезка можно заменить на побитовый сдвиг

[volselongames]

Александр добрый день, у тебя в видео есть формула M = F(k + 1) - (N + 1);
если что ты про неё рассказываешь на 7 минуте 40 секунде в видео, ты говоришь то что поиск Фибоначчи работает особенно быстро если, F(k + 1) == N + 1, если это условие не выполняется то, вводим дополнительное число M, которое вычисляется по формуле, M = F(k + 1) - (N + 1) - это число M позволяет распространить поиск Фибоначчи на массив любой длины, а если допустим случится так, что F(k + 1) == N + 1 - это условие выполнится, то число M вводить не обязательно?
или его вводим в любом случае?

[ВіталійЗіновєв-щч]

Реализация алгоритма на typescript

const getFibonacciNumber = (k: number): number => {
let firstNumber = 0
let secondNumber = 1
for (let i = 0; i < k; i++) {
const temp = secondNumber
secondNumber += firstNumber
firstNumber = temp
}
return firstNumber
}

export const fibonacciSearch = (arr: number[], el: number) => {
const sequince = [0]
for (let i = 1; sequince[sequince.length - 1] < arr.length; i++) {

}
const lastFibonacciNumber = sequince.pop() as number
const offset = lastFibonacciNumber - arr.length // 13 - 11 = 2
let i = (sequince.pop() as number) - offset // 8 - 2 = 6
while (true) {
const moveToRight = i < 0 || arr[i] < el
const moveToLeft = !(i < arr.length) || el < arr[i]
if (moveToRight || moveToLeft) {
const canMove = sequince.length === 2 // [0, 1]
if (canMove) break
const offset = sequince.pop() as number // 5 3 2 1
i += offset * (moveToRight ? 1 : -1)
continue
}
return i // found
}
return -1
}