Binäres Suchen
-
Hi,
wie kann ich die maximalen Suchschritte beim binären Suchen berechnen?
Bei 34 Datensätzen benötige ich beim sequentiellen Suchen maximal 34 Suchschritte. Wie ist das beim binären Suchen? Bei 34 Datensätzen benötigt man meiner Meinung nach maximal 6 Suchschritte. Dies habe ich jetzt grafisch gelöst. Gibt es dafür eine rechnerische Lösung? Wenn ich z. B. 2000 Datensätze habe wäre die grafische Lösung sehr aufwändig.
-
ceil(ld(n))
-
-
n = Anzahl der Datensätze
ld = Logarithmus zur Basis 2
ceil = "aufrunden"
...was rauskommt ist die maximale Anzahl der Suchschritte.
-
Danke.
-
ld? heißt das nicht lg oder log?
-
Nein, ld ist Logarithmus zur Basis 2. lg wäre Basis 10, log je nach Konvention braucht man noch ne Basis oder es ist Basis e.
Da hier bei jedem Schritt die Menge halbiert wird braucht man den ld um die Schrittanzahl zu kriegen.Im O-Kalkül hingegen kann man genausogut log schreiben, weil sich die ganzen Logarithmen nur um feste Koeffizienten unterscheiden. Und sowas fällt im O-Kalkül eben weg. Daher ist binäre Suche dann auch in O(log n).
MfG Jester
-
Steht das d für dual oder sowas?
-
. schrieb:
Steht das d für dual oder sowas?
"Logarithmus Dualis" um genau zu sein.