Algorithme de recherche approximative dans la liste d'entiers triés

Question

Considérons un tableau d'entiers (supposé être trié); Je voudrais trouver l'indice de tableau de l'entier le plus proche d'un entier donné de la manière la plus rapide possible. Et le cas où il y a plusieurs possibilités, l'algorithme devrait tout identifier. Exemple: considérons T = (3, 5, 24, 65, 67, 87, 129, 147, 166), et si l'entier donné est 144, alors le code doit identifier 147 comme l'entier le plus proche, et donner l'indice de tableau 7 correspondant à cette entrée. Pour le cas de 66, l'algorithme devrait identifier 65 et 67.

Existe-t-il des algorithmes O (1) ou au moins O (log N) pour ce faire? L'implémentation de l'algorithme de recherche directe (recherche binaire, recherche arborescente, hachage, etc.) ne fonctionnera pas, car celles-ci nécessiteraient une correspondance parfaite. Est-il possible de les modifier pour gérer la recherche approximative?

Je développe un code C.

Merci

Answer 1

Do recherche binaire jusqu'à ce que vous obtenez à un seul élément. S'il y a un match, marchez le long de vos voisins pour trouver d'autres matchs. S'il n'y a pas de correspondance, regardez vos voisins immédiats pour trouver la correspondance la plus proche.

Answer 2

Correctement mis en œuvre binary-search devrait faire l'affaire - aussi longtemps que vous identifiez le moment où votre gamme de recherche a diminué à deux éléments seulement. Ensuite, il vous suffit de choisir le plus proche. Complexité: O (log n).