Binäre Suche oder lineare Suche in großen unsortierten Listen?

Question

Ich verstehe, dass die Binary Suche effizienter als die Linear Suche in einer ist sortierte Liste und eine große Liste, aber was ist, wenn wir eine große Liste haben aber nicht sortiert, die eine wir lineare Suche verwenden oder binäre Suche?

Answer 1

Das Konzept der binäre Suche kann nur auf sortierten Eingaben arbeiten. Recherchiere einfach wie es funktioniert: Binary search at Wikipedia.

Basierend auf Ihre ursprüngliche Frage „binäre Suche oder lineare Suche auf unsortierten Listen?“ die Antwort ist eindeutig lineare Suche weil binäre Suche nicht verwendet werden kann.

Allerdings könnte es möglich sein, dass Sie mindestens einige Kenntnisse der Eingangsstruktur haben? Wenn ja könnte Sie das verwenden, um eine bessere Lösung zu erstellen. Wenn es völlig zufällig ist, dann ist die lineare Suche offensichtlich die beste. Aber Sie könnten die Suche leicht parallelisieren, wie hier zu sehen: Fastest way to search for an element in unsorted array.

---

Lassen Sie mich Ihnen einen kleinen Überblick für die binäre Suche geben. Ich wähle eine Zufallszahl zwischen 1 und 100. Sie können jetzt die Nummer erraten und ich werde Ihnen sagen, ob meine Nummer niedriger, gleich oder größer als Ihre Schätzung ist.

Binary Suche würde jetzt denke, die Hälfte des Suchintervalls, . Ich antworte die Vermutung ist zu hoch. Das Suchintervall ist jetzt von 1 bis 49 und die binäre Suche geht jetzt für . Es wiederholt die Suche, bis das Element gefunden wurde.

---

Wenn Sie Ihre Eingabe ist unsortiert dann wird dies, weil nicht mehr funktionieren, wenn ich Ihnen sagen, dass mein Element niedriger als ist dann bedeutet dies nicht zwangsläufig bedeuten, dass es zu 50 links gespeichert ist, es könnte auch auf der rechten Seite sein, weil der Eingang unsortiert ist.

Hier ist ein Bild, das das Algorithmus (durch eine schnelle Google-Suche gefunden):

Answer 2

In diesem Fall Linear Search wird effizienter sein, weil seine Komplexität O(n) ist.

Aber für binäre Suche das Array muss sortiert sein. Zum Sortieren der besten Komplexität wird O(nlogn), und die Suche in O(logn), die, wenn hinzugefügt, gibt O(nlogn).

Also, klar Lineare Suche ist hier besser.

Answer 3

Binärsuche per Definition nur für sortierte Sequenzen. Voraussetzung ist, dass die Liste, nach der Sie suchen, sortiert wird, da sonst die Binärsuche überhaupt nicht funktioniert.

So Sie die Frage zu beantworten: Auf unsortierten Reihenfolge lineare Suche ist der Weg

Aber im Auge behalten zu gehen, dass, wenn Sie eine Reihe ausführen müssen (sagen M) sucht dann könnte es Es ist gut, die Liste einmal zu sortieren und dann die Binärsuche zu verwenden.

Stellen Sie sich vor, Sie müssen M Suchen auf einem Array der Länge N durchführen. -

• Mit lineare Suche kosten würde N*M (M durchsucht jede Kalkulation N).
• Sortierung + binäre SucheO((N log N)+(log N)*M) kosten würde ->(N Log N) zum Sortieren der Liste plus M sucht jede Log N kostet

Wann ist es bequem, die ehemalige und als dieser? wenn N*M >N log N+(log N)*M.