HeIp compréhension Fibonacci Recherche

Question

Sur Internet, je ne trouve que du code pour l'algorithme, mais je dois d'abord comprendre sous forme de texte parce que j'ai du mal à comprendre les choses à partir du code seulement. Et d'autres descriptions de l'algorithme sont très compliquées pour moi (sur Wikipedia et autres sites).

Voici ce que je comprends pour beaucoup:

Disons que nous voulons rechercher dans le tableau l'élément 10:

Index i 0 1 2 3 4 
     2 3 4 10 40 

Certains numéro de fibonacci ici:

Index j 0 1 2 3 4 5 6 7 8 9 
     0 1 1 2 3 5 8 13 21 34 

La première chose que nous faisons On trouve un nombre de fibonacci supérieur à la longueur du tableau. La longueur du tableau est 4 donc nous devons prendre le numéro de fibonacci 5 qui est dans la position d'index j=5.

Mais où diviser le tableau maintenant et comment continuer? Je ne comprends vraiment pas .. S'il vous plaît aider à comprendre pour l'examen ...

Answer 1

L'algorithme va de la façon suivante: La longueur du tableau est 5, donc le nombre de fibonacci qui est supérieur ou égal à 5 5. Les deux nombres qui précèdent dans la séquence de Fibonacci sont 2 [n-2] et 3 [n-1] - (2, 3, 5).

Ainsi, arr [n-2] ie arr [2] est comparé avec le nombre à rechercher qui est 10.

Si l'élément est plus petit que le nombre, la séquence est décalée vers une heure la gauche. De plus, l'index précédent est enregistré pour l'itération suivante afin de donner un décalage à l'index. Dans ce cas, puisque 4 est plus petit, n-2 devient 1 (1, 2, 3). arr [1 + 2 (prev)] = arr [3] = 10. Donc, l'indice du nombre est 3.

Si l'élément est plus grand, la séquence est décalée de 2 fois vers la gauche.

Toujours l'élément min (n-2 + offset, n) ème est comparé avec le nombre pour obtenir le résultat correspondant.