schnellste Möglichkeit zu bestimmen, ob ein Element in einem sortierten Array ist

Question

Ich habe ein Array von sortierten Ints mit einem 1.000 oder mehr Werte (könnte bis zu 5000 +). Ich muss eine Funktion schreiben, die ein int empfängt und ein bool basierend auf dem Element zurückgibt, das sich in dem Array befindet. Ich weiß, dass ich eine for-Schleife mit einer Pause schreiben kann, ich weiß, dass ich jquery .InArray verwenden kann.

Was wäre der beste Weg, dies zu implementieren, WISSEN, dass das Array sortiert ist.

Danke.

Answer 1

Mit dem Wissen, dass das Array sortiert ist, wäre eine binäre Suche der beste Ansatz.

Answer 2

Wenn das Array sortiert ist, dann ist die Antwort sortiert - verwenden Sie ein binäres Chop.

Answer 3

Ich denke, dass Sie eine binäre Suchroutine verwenden möchten. Eine binäre Suchroutine ist , während eine lineare Suche im Durchschnitt ist.

Es gibt viele Variationen, um Form zu wählen. Hier ist ein ich in this article gefunden:

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; 
} 

Oder diese einfache aussehende Version von this article, die eine binären Suchfunktion in zig verschiedenen Sprachen hat.

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; 
} 

Es gibt auch eine binäre Suche in Google-Verschluss mit dem Code here.

Und eine gute Beschreibung, wie der binäre Suchalgorithmus funktioniert Wikipedia.

Answer 4

Viele Sprachen haben dies bereits implementiert, zum Beispiel in Java können Sie einfach CollectionsCollections.binarySearch (Liste> Liste, T-Taste) -Methode verwenden und ich bin mir ziemlich sicher, dass C# auch eine Art von BinarySearch-Methode hat.

Answer 5

Wenn Suchvorgänge mehr als einmal ausgeführt werden, migrieren Sie zu einem kartenähnlichen Objekt.

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

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