schnellster Weg, um festzustellen, ob sich ein Element in einem sortierten Array befindet

7

Ich habe ein Array von sortierten Ints mit 1.000 oder mehr Werten (kann bis zu 5000+ sein). 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.

    
frenchie 22.04.2012, 00:32
quelle

5 Antworten

9

Wenn Sie wissen, dass das Array sortiert ist, wäre eine binäre Suche der beste Ansatz.

    
g.d.d.c 22.04.2012, 00:33
quelle
8

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

Es gibt viele Variationen, um ein Formular zu wählen. Hier ist eine, die ich in diesem Artikel gefunden habe:

%Vor%

Oder diese einfachere Version von diesem Artikel , die eine binäre Suchfunktion in einer Vielzahl von Sprachen hat.

%Vor%

Es gibt auch eine binäre Suche in Google Closure mit dem Code hier .

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

    
jfriend00 22.04.2012 00:49
quelle
3

Wenn das Array sortiert ist, dann ist die Antwort sortiert - benutze einen binären Chop.

    
Martin James 22.04.2012 00:34
quelle
0

Wenn Sie Suchvorgänge mehr als einmal durchführen, migrieren Sie zu einem kartenähnlichen Objekt.

%Vor%
    
user1212212 26.05.2017 20:39
quelle
-1

Viele Sprachen haben dies bereits implementiert, zum Beispiel in Java. Sie können einfach die Methode CollectionsCollections.binarySearch (List & gt; list, T key) verwenden und ich bin mir ziemlich sicher, dass C # auch eine Art BinarySearch-Methode hat.

    
Merf 07.05.2012 17:15
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset R ggplot: geom_tile Zeilen in PDF-Ausgabe