Bei der zweiten Code-Kata (bei der Sie aufgefordert werden, fünf Mal einen binären Suchalgorithmus zu implementieren, jedes Mal mit einer anderen Methode) habe ich eine etwas andere Lösung gefunden, die wie folgt funktioniert:
Wenn ich ein sortiertes Array mit einer Länge von 100 habe und sehe, dass sein Startfeld die Nummer 200 und sein Endfeld die Nummer 400 enthält, würde ich als Mathematikstudent wahrscheinlich anfangen, Feld 35 zu durchsuchen, wenn ich das suche 270 und nicht das Feld 50 wie bei einem normalen binären Suchalgorithmus.
Wenn die Nummer in Feld 35 des Arrays 270 ist, ist 35 der Index, nach dem ich gesucht habe.
Wenn das nicht der Fall ist, kann ich die Zahl vergleichen (sagen wir 280) und die Operation wiederholen, indem ich den unteren Teil des Arrays nehme (also habe ich 35 Felder, wobei das Startfeld 200 enthält und das Endfeld 280 enthält), wenn die Die Zahl, die ich gefunden habe, ist größer als das, wonach ich gesucht habe, oder der obere Teil des Arrays (sagen wir, ich habe 260: jetzt habe ich 65 Indizes, der erste 260 und der letzte 400. Orientativ würde ich aufwärts gehen Index 4 dieses Sub-Arrays (Index 39 des gesamten Arrays), wenn die Zahl, die ich erhalten habe, kleiner ist als die Zahl, nach der ich suche.
Die Frage ist: Kann dieser Algorithmus als binärer Suchalgorithmus angesehen werden? Wenn nicht, hat es einen eigenen Namen?
quelle
Antworten:
Ich würde das keine binäre Suche nennen.
Es ähnelt eindeutig der binären Suche und ist natürlich eine Verfeinerung der binären Suche. Die Komplexitätsmerkmale des Algorithmus unterscheiden sich jedoch erheblich. Die Interpolationssuche hat eine Laufzeit von O (log (log (n)) erwartet, vorausgesetzt, die Daten sind gleichmäßig verteilt. Dies wird jedoch durch die Laufzeit von O (n) im ungünstigsten Fall bezahlt.
Ich sage lieber "Die Laufzeit der Binärsuche im ungünstigsten Fall ist O (log (n))" als "Abhängig von der Auswahl der Begrenzungselemente beträgt die Laufzeit der Binärsuche im ungünstigsten Fall O (log (n))". Dies bedeutet, dass ich die Interpolationssuche nicht als binären Suchalgorithmus klassifizieren kann.
quelle
quelle
Ich denke, die richtige Terminologie wäre dychotomisch überlegte Suche.
Sie suchen in einem flachen Array mit anschließendem überlegten Suchen basierend auf der angenommenen flachen Verteilung der darin enthaltenen Zahlen.
Dies entspricht der Art und Weise, wie eine Person ein Wort in einem Wörterbuch suchen würde. Es kann jedoch sehr ineffizient sein, wenn die Verteilung der Daten unregelmäßig ist.
quelle