Ricerca nei rapporti sugli array “non trovato” anche se è stato trovato

Questa è una domanda generica e una risposta per un errore logico che ho visto in molte domande dei nuovi programmatori in una varietà di lingue.

Il problema è cercare un array per un elemento che corrisponde ad alcuni criteri di input. L’algoritmo, in pseudo-codice, assomiglia a questo:

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" 

Questo codice riporta “Non trovato” anche se trova correttamente un elemento corrispondente.

Il problema è che quando stai cercando qualcosa in modo lineare attraverso un array, non puoi sapere che non è stato trovato finché non raggiungi la fine dell’array. Il codice nella domanda riporta “Not found” per ogni elemento non corrispondente, anche se potrebbero esserci altri elementi corrispondenti.

La semplice modifica consiste nell’utilizzare una variabile che tiene traccia se hai trovato qualcosa, e quindi controlla questa variabile alla fine del ciclo.

 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 ha un else: block nei suoi loop for . Questo esegue il codice solo se il ciclo viene eseguito fino al completamento, anziché terminare a causa dell’utilizzo dell’interruzione. Questo ti permette di evitare la variabile found (anche se potrebbe ancora essere utile per l’elaborazione successiva):

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

Alcune lingue hanno meccanismi integrati che possono essere usati invece di scrivere il tuo loop.

  • Alcune lingue hanno una o any funzione che accetta una funzione di callback e restituisce un valore booleano che indica se ha esito positivo per qualsiasi elemento dell’array.
  • Se la lingua ha una funzione di filtro degli array, è ansible filtrare l’array di input con una funzione che verifica i criteri e quindi verificare se il risultato è un array vuoto.
  • Se stai cercando di associare esattamente un elemento, la maggior parte delle lingue fornisce una funzione di find o index che cercherà un elemento corrispondente.

Se si effettuano ricerche frequenti, potrebbe essere preferibile convertire l’array in una struttura dati che può essere ricercata in modo più efficiente. La maggior parte delle lingue fornisce strutture di dati di hash table set e / o hash table (quest’ultima va sotto molti nomi a seconda della lingua, ad esempio array associativo, mappa, dizionario), e queste sono tipicamente ricercabili in O (1) tempo, mentre la scansione di un array è O (n).