infa_1 / 15.Фибоначчиев поиск

15.Фибоначчиев поиск.

В этом поиске анализируются элементы, находящиеся в позициях равных числам Фибоначчи.

Числа Фибоначчи.

{1,2,3,5,8,13,21,34,55}

Поиск продолжается до тех пор, пока не будет найден интервал между 2-мя ключами, где может располагаться отыскиваемый ключ.

Например:

Дано исходное множество ключей {3,5,8,9,11,14,15,19,21,22,28,33,35,37,42,45,48,54}

Отыскиваемый ключ К=42

1 шаг. k ᴜ k₁

42>3 => отыскиваемый ключ уравнивается с ключом, стоящим в позиции равной числам Фибоначчи.

2 шаг. k ᴜ k₂

42>5 => выбирается следующее число Фибоначчи, стоящее в соответствующей позиции.

3 шаг. k ᴜ k₃

42>8=> сравнение продолжается

4 шаг. k ᴜ k₅

42>11 => сравнение продолжается

5 шаг. k ᴜ k₈ 42>19

6 шаг. k ᴜ k₁₃ 42>35

7 шаг. k ᴜ k₁₈

42<52 => найден интервал, в котором находится отыскиваемый ключ от 13 до 18.

8 шаг. k ᴜ k₁ 42>35

9 шаг. k ᴜ k₂ 42>37

10 шаг. K=42 => найден.