Le tableau signale « introuvable » bien qu'il ait été trouvé : un dilemme de recherche déroutant

Question

Il s'agit d'une question et d'une réponse courantes avec une erreur logique que je vois dans de nombreuses questions posées par les nouveaux programmeurs dans différents langages.

Le problème est de rechercher dans un tableau les éléments qui correspondent à certains critères de saisie. Le pseudocode de l'algorithme est le suivant :

for each element of Array:
    if element matches criteria:
        do something with element
        maybe break out of loop (if only interested in first match)
    else:
        print "Not found"

Ce code affichera « Introuvable » même si l'élément correspondant est trouvé avec succès.

Answer 1

Le problème est que lorsque vous recherchez linéairement quelque chose dans un tableau, vous ne savez pas qu'il n'a pas été trouvé avant d'atteindre la fin du tableau. Le code dans la question indique « introuvable » pour chaque élément sans correspondance, même s'il peut y avoir d'autres éléments correspondants.

Une modification simple consisterait à utiliser une variable pour savoir si vous avez trouvé quelque chose, puis à vérifier cette variable à la fin de la boucle.

found = false
for each element of Array:
    if element matches criteria:
        do something with element
        found = true
        maybe break out of loop (if only interested in first match)

if not found:
    print "Not found"

Python dans sa variable for 循环中有一个 else: 块。仅当循环运行完成时才执行代码，而不是由于使用 break 而结束。这使您可以避免 found (même si cela peut encore être utile pour un traitement ultérieur) :

for element in someIterable:
    if matchesCriteria(element):
        print("Found")
        break
else:
    print("Not found")

Certains langages ont des mécanismes intégrés qui peuvent être utilisés au lieu d'écrire vos propres boucles.

• Certaines langues ont des fonctions any 或 some qui acceptent une fonction de rappel et renvoient une valeur booléenne indiquant si la fonction a réussi pour n'importe quel élément du tableau.
• Si le langage dispose d'un filtrage de tableau, vous pouvez filtrer le tableau d'entrée à l'aide d'une fonction qui vérifie une condition puis vérifie si le résultat est un tableau vide.
• Si vous essayez de faire correspondre exactement un élément, la plupart des langues proposent une fonction find 或 index pour rechercher un élément correspondant.

Si vous effectuez des recherches fréquemment, il est préférable de convertir le tableau en une structure de données qui peut être recherchée plus efficacement. La plupart des langages fournissent des structures de données 集合和/或哈希表 (ces dernières portent plusieurs noms selon la langue, par exemple tableaux associatifs, cartes, dictionnaires), celles-ci prennent généralement un temps O(1) pour rechercher et un temps O(n) pour analyser le tableau.