Suche…
Binäre Suche
Einführung
Die binäre Suche ist ein Suchalgorithmus zum Teilen und Erobern. Es verwendet O(log n) -Zeit, um die Position eines Elements in einem Suchraum zu finden, wobei n die Größe des Suchraums ist.
Bei der binären Suche wird der Suchraum bei jeder Iteration halbiert, nachdem der Zielwert mit dem mittleren Wert des Suchraums verglichen wird.
Um die binäre Suche verwenden zu können, muss der Suchbereich auf eine bestimmte Weise sortiert (sortiert) werden. Doppelte Einträge (solche, die gemäß der Vergleichsfunktion als gleich angesehen werden) können nicht unterschieden werden, obwohl sie die Eigenschaft der binären Suche nicht verletzen.
Üblicherweise verwenden wir weniger als (<) als Vergleichsfunktion. Wenn a <b, wird true zurückgegeben. wenn a nicht weniger als b und b nicht weniger als a ist, sind a und b gleich.
Beispielfrage
Sie sind ein Ökonom, aber ein ziemlich schlechter. Sie haben die Aufgabe, den Gleichgewichtspreis (dh den Preis, für den das Angebot = Nachfrage ist) für Reis zu ermitteln.
Denken Sie daran, je höher der Preis festgelegt ist, desto größer ist das Angebot und desto geringer ist die Nachfrage
Da Ihr Unternehmen die Marktkräfte sehr effizient berechnet, können Sie Angebot und Nachfrage in Reiseinheiten sofort abrufen, wenn der Reispreis auf einen bestimmten Preis p .
Ihr Chef möchte den Gleichgewichtspreis so schnell wie möglich, teilt Ihnen jedoch mit, dass der Gleichgewichtspreis eine positive ganze Zahl sein kann, die höchstens 10^17 beträgt, und es gibt garantiert genau eine positive ganze Zahl im Bereich. Machen Sie sich also mit Ihrem Job auf, bevor Sie ihn verlieren!
Sie können die Funktionen getSupply(k) und getDemand(k) , die genau das tun, was im Problem angegeben ist.
Beispiel Erklärung
Hier ist unser Suchraum von 1 bis 10^17 . Eine lineare Suche ist daher nicht machbar.
Beachten Sie jedoch, daß , wenn der k nach oben geht, getSupply(k) zunimmt und getDemand(k) abnimmt. Daher ist für x > y getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Daher ist dieser Suchraum monoton und wir können die binäre Suche verwenden.
Der folgende Pseudokode demonstriert die Verwendung der binären Suche:
high = 100000000000000000 <- Upper bound of search space
low = 1 <- Lower bound of search space
while high - low > 1
mid = (high + low) / 2 <- Take the middle value
supply = getSupply(mid)
demand = getDemand(mid)
if supply > demand
high = mid <- Solution is in lower half of search space
else if demand > supply
low = mid <- Solution is in upper half of search space
else <- supply==demand condition
return mid <- Found solution
Dieser Algorithmus läuft in ~O(log 10^17) Zeit. Dies kann auf die Zeit ~O(log S) verallgemeinert werden, wobei S die Größe des Suchraums ist, da bei jeder Iteration der while Schleife der Suchraum halbiert wurde ( von [niedrig: hoch] auf entweder [niedrig: mittel] oder [Mitte: hoch] ).
C Implementierung der binären Suche mit Rekursion
int binsearch(int a[], int x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid]) {
return (mid);
} else
if (x < a[mid]) {
binsearch(a, x, low, mid - 1);
} else {
binsearch(a, x, mid + 1, high);
}
}
Binäre Suche: Nach sortierten Zahlen
Es ist am einfachsten, eine binäre Suche nach Zahlen mit Pseudo-Code anzuzeigen
int array[1000] = { sorted list of numbers };
int N = 100; // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for
low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found
Versuchen Sie nicht, zu einem frühen Zeitpunkt zurückzukehren, indem Sie array [mid] mit x für Gleichheit vergleichen. Der zusätzliche Vergleich kann den Code nur verlangsamen. Beachten Sie, dass Sie einen niedrigen Wert hinzufügen müssen, um zu vermeiden, dass die Ganzzahldivision immer abgerundet wird.
Interessanterweise können Sie mit der obigen Version der binären Suche das kleinste Vorkommen von x im Array finden. Wenn das Array Duplikate von x enthält, kann der Algorithmus leicht modifiziert werden, um das größte Vorkommen von x zurückzugeben, indem er einfach die if-Bedingung hinzufügt:
while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}
Beachten Sie, dass Sie anstelle von mid = (low + high) / 2 auch eine gute Idee sein können, mid = low + ((high - low) / 2) für Implementierungen wie Java-Implementierungen zu verwenden, um das Risiko einer Überlauf für wirklich große Eingänge.
Lineare Suche
Die lineare Suche ist ein einfacher Algorithmus. Sie durchläuft Elemente, bis die Abfrage gefunden wurde, was sie zu einem linearen Algorithmus macht - die Komplexität ist O (n), wobei n die Anzahl der Elemente ist, die durchlaufen werden.
Warum O (n)? Im schlimmsten Fall müssen Sie alle n Elemente durchgehen.
Es ist vergleichbar mit der Suche nach einem Buch in einem Stapel von Büchern - Sie gehen alle durch, bis Sie das gewünschte Buch gefunden haben.
Unten ist eine Python-Implementierung:
def linear_search(searchable_list, query):
for x in searchable_list:
if query == x:
return True
return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True
Rabin Karp
Der Rabin-Karp-Algorithmus oder der Karp-Rabin-Algorithmus ist ein Zeichenfolgen-Suchalgorithmus, der Hashes verwendet, um einen Satz von Musterzeichenfolgen in einem Text zu finden. Seine durchschnittliche und beste Laufzeit beträgt O (n + m) im Raum O ( p), aber die Zeit im ungünstigsten Fall ist O (nm), wobei n die Länge des Textes und m die Länge des Musters ist.
Algorithmusimplementierung in Java zum String-Matching
void RabinfindPattern(String text,String pattern){
/*
q a prime number
p hash value for pattern
t hash value for text
d is the number of unique characters in input alphabet
*/
int d=128;
int q=100;
int n=text.length();
int m=pattern.length();
int t=0,p=0;
int h=1;
int i,j;
//hash value calculating function
for (i=0;i<m-1;i++)
h = (h*d)%q;
for (i=0;i<m;i++){
p = (d*p + pattern.charAt(i))%q;
t = (d*t + text.charAt(i))%q;
}
//search for the pattern
for(i=0;i<end-m;i++){
if(p==t){
//if the hash value matches match them character by character
for(j=0;j<m;j++)
if(text.charAt(j+i)!=pattern.charAt(j))
break;
if(j==m && i>=start)
System.out.println("Pattern match found at index "+i);
}
if(i<end-m){
t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
if(t<0)
t=t+q;
}
}
}
Bei der Berechnung des Hashwerts dividieren wir ihn durch eine Primzahl, um eine Kollision zu vermeiden. Nach der Division durch die Primzahl sind die Kollisionswahrscheinlichkeiten geringer, aber es besteht immer noch die Möglichkeit, dass der Hashwert für zwei Zeichenfolgen derselbe sein kann Wir erhalten eine Übereinstimmung, die wir Zeichen für Zeichen überprüfen müssen, um sicherzustellen, dass wir eine korrekte Übereinstimmung haben.
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m))% q;
Hiermit wird der Hashwert für Muster neu berechnet, indem zuerst das am weitesten links stehende Zeichen entfernt und dann das neue Zeichen aus dem Text hinzugefügt wird.
Analyse der linearen Suche (schlechteste, durchschnittliche und beste Fälle)
Wir können drei Fälle haben, um einen Algorithmus zu analysieren:
Schlimmsten Fall
Durchschnittlicher Fall
I'm besten fall
#include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) { int i; for (i=0; i<n; i++) { if (arr[i] == x) return i; } return -1; }/ * Treiberprogramm zum Testen der obigen Funktionen * /
int main() { int arr[] = {1, 10, 30, 15}; int x = 30; int n = sizeof(arr)/sizeof(arr[0]); printf("%d is present at index %d", x, search(arr, n, x)); getchar(); return 0; }
Worst-Case-Analyse (normalerweise erledigt)
In der Worst-Case-Analyse berechnen wir die Obergrenze der Laufzeit eines Algorithmus. Wir müssen den Fall kennen, bei dem die maximale Anzahl von Operationen ausgeführt wird. Bei der linearen Suche tritt der ungünstigste Fall auf, wenn das zu durchsuchende Element (x im obigen Code) nicht im Array vorhanden ist. Wenn x nicht vorhanden ist, werden die search () - Funktionen nacheinander mit allen Elementen von arr [] verglichen. Daher wäre die Zeitkomplexität der linearen Suche im ungünstigsten Fall Θ (n).
Durchschnittliche Fallanalyse (manchmal durchgeführt)
Bei der Durchschnittsfallanalyse nehmen wir alle möglichen Eingaben und berechnen die Berechnungszeit für alle Eingaben. Addieren Sie alle berechneten Werte und teilen Sie die Summe durch die Gesamtzahl der Eingaben. Wir müssen die Verteilung von Fällen kennen (oder vorhersagen). Nehmen wir für das lineare Suchproblem an, dass alle Fälle gleichmäßig verteilt sind (einschließlich des Falles, in dem x nicht im Array vorhanden ist). Also summieren wir alle Fälle und dividieren die Summe durch (n + 1). Es folgt der Wert der durchschnittlichen Fallzeitkomplexität.
Best Case Analyse (Bogus)
In der Best-Case-Analyse berechnen wir die Untergrenze der Laufzeit eines Algorithmus. Wir müssen den Fall kennen, der die Ausführung einer Mindestanzahl von Operationen bewirkt. Beim linearen Suchproblem tritt der beste Fall auf, wenn x am ersten Ort vorhanden ist. Die Anzahl der Operationen ist im besten Fall konstant (unabhängig von n). Die Zeitkomplexität im besten Fall wäre also Θ (1). In den meisten Fällen führen wir Worst-Case-Analysen durch, um Algorithmen zu analysieren. In der schlechtesten Analyse garantieren wir eine obere Grenze für die Laufzeit eines Algorithmus, der gute Informationen darstellt. Die durchschnittliche Fallanalyse ist in den meisten praktischen Fällen nicht einfach und wird selten durchgeführt. In der Durchschnittsfallanalyse müssen wir die mathematische Verteilung aller möglichen Eingaben kennen (oder vorhersagen). Die Best-Case-Analyse ist falsch. Das Gewährleisten einer unteren Schranke eines Algorithmus liefert keine Informationen, da im schlimmsten Fall ein Algorithmus Jahre dauern kann.
Bei einigen Algorithmen sind alle Fälle asymptotisch gleich, dh es gibt keine ungünstigsten und besten Fälle. Zum Beispiel Merge Sort. Merge Sort führt in allen Fällen Θ (nLogn) -Operationen durch. Die meisten anderen Sortieralgorithmen weisen die schlechtesten und besten Fälle auf. Bei der typischen Implementierung von Quick Sort (bei dem Pivot als Eckelement gewählt wird) tritt beispielsweise der schlechteste Fall auf, wenn das Eingabearray bereits sortiert ist, und das Beste, wenn die Pivotelemente das Array immer in zwei Hälften teilen. Bei der Einfügungssortierung tritt der schlechteste Fall auf, wenn das Array umgekehrt sortiert wird, und der beste Fall, wenn das Array in der gleichen Reihenfolge wie die Ausgabe sortiert wird.