modo più rapido per determinare se un elemento si trova in un array ordinato

Question

Ho una matrice di valori ordinati con 1.000 o più valori (potrebbe essere fino a 5000+). Ho bisogno di scrivere una funzione che riceve un int e restituisce un bool in base all'elemento presente nell'array. So che posso scrivere un ciclo for con una pausa, so che posso usare jquery .InArray.

Quale sarebbe il modo migliore per implementare questo, SAPERE che l'array è ordinato.

Grazie.

Answer 1

Sapendo che l'array è ordinato, una ricerca binaria sarebbe l'approccio migliore.

Answer 2

Se la matrice è ordinata, quindi la risposta è ordinata, utilizzare un chop binario.

Answer 3

Penso che tu voglia usare una routine di ricerca binaria. Una routine di ricerca binaria è mentre una ricerca lineare è, in media, .

Ci sono molte varianti per scegliere la forma. Ecco quello che ho trovato in this article:

function binarySearch(items, value){ 

    var startIndex = 0, 
     stopIndex = items.length - 1, 
     middle  = Math.floor((stopIndex + startIndex)/2); 

    while(items[middle] != value && startIndex < stopIndex){ 

     //adjust search area 
     if (value < items[middle]){ 
      stopIndex = middle - 1; 
     } else if (value > items[middle]){ 
      startIndex = middle + 1; 
     } 

     //recalculate middle 
     middle = Math.floor((stopIndex + startIndex)/2); 
    } 

    //make sure it's the right value 
    return (items[middle] != value) ? -1 : middle; 
} 

O questo semplice versione guardando da this article che ha una funzione di ricerca binaria in un triliardo di lingue diverse.

function binary_search_iterative(a, value) { 
    var lo = 0, hi = a.length - 1, mid; 
    while (lo <= hi) { 
     mid = Math.floor((lo+hi)/2); 
     if (a[mid] > value) 
      hi = mid - 1; 
     else if (a[mid] < value) 
      lo = mid + 1; 
     else 
      return mid; 
    } 
    return null; 
} 

C'è anche una ricerca binaria in chiusura di Google con il codice here.

E, una buona descrizione di come funziona l'algoritmo di ricerca binaria su Wikipedia.

Answer 4

Molte lingue lo hanno già implementato, ad esempio in java è possibile utilizzare solo il metodo CollectionsCollections.binarySearch (Elenco> elenco, tasto T) e sono abbastanza sicuro che C# abbia anche una sorta di metodo BinarySearch.

Answer 5

Se si effettuano ricerche più di una volta, eseguire la migrazione a un oggetto simile alla mappa.

var fastLookup = {}; 
 
mySortedArray.forEach(function(i){fastLookup[i]=true)}); 
 

 
//Each time: 
 
    if (fastLookup[key]===true){ //do thing 
 
    }