Publié · en amélioration
Algorithm
Les algorithmes de recherche trouvent valeurs et positions : recherche linéaire et dichotomique, lower_bound, upper_bound, recherche sur la réponse, hachage.
Rechercher, c'est trouver une valeur dans une collection de données, ou la position à partir de laquelle une condition devient vraie. La recherche linéaire examine les éléments un par un et s'applique à n'importe quelles données, tandis que la recherche dichotomique divise par deux un intervalle trié à chaque étape et n'a besoin que d'une vingtaine de comparaisons pour un million d'éléments. Pour une correspondance exacte, une table de hachage répond en temps constant en moyenne.
La recherche est fondamentale, car presque tous les programmes consultent des données : index de bases de données, autocomplétion, analyse de journaux et tables de routage en dépendent. La recherche dichotomique ne se limite d'ailleurs pas aux tableaux. Dès qu'une condition oui/non ne change qu'une seule fois sur un intervalle, on peut chercher la réponse elle-même par dichotomie, ce qui transforme de nombreux problèmes d'optimisation d'entretiens techniques en code court et fiable.
Commencez par écrire vous-même une recherche linéaire et une recherche dichotomique sur intervalle fermé, puis entraînez-vous aux formes lower_bound et upper_bound sur intervalle semi-ouvert jusqu'à ce que la gestion des bornes devienne naturelle. Déroulez de petits exemples à la main, comparez votre code au module bisect de Python avec des entrées aléatoires, puis abordez la recherche sur la réponse et la recherche ternaire avec des problèmes d'optimisation.
Compare les éléments un par un en temps O(n). Elle ne demande aucun tri et reste souvent le choix le plus rapide pour de petites collections.
Divise par deux un intervalle trié à chaque étape et trouve une valeur en O(log n). La version itérative n'utilise que O(1) de mémoire supplémentaire.
Renvoient la première position dont la valeur est supérieure ou égale, ou strictement supérieure, à la cible. Leur différence compte les doublons, et le module bisect de Python fournit les deux.
La recherche paramétrique transforme la question de la plus petite valeur réalisable en un test oui/non et explore par dichotomie l'intervalle des réponses possibles.
lower_bound renvoie le premier indice dont la valeur est supérieure ou égale à x, en travaillant sur l'intervalle semi-ouvert [lo, hi). Si la valeur du milieu est inférieure à x, la moitié gauche est écartée, sinon la moitié droite. contains s'appuie sur cet indice pour tester la présence de la valeur, et la dernière ligne vérifie que le résultat correspond à bisect.bisect_left de la bibliothèque standard.
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.pySix chapitres pour aller de l'installation aux notions essentielles de Recherche.
Posez vos questions, partagez votre expérience et échangez vos avis sur Recherche.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.