in sortierte liste sortiert einfügen

[Medium]

Binäre Suche ist sicherlich das schnellste für beliebige Daten deren Verteilung man überhaupt nicht einschätzen kann. Je gleichmäßiger die Einträge verteilt sind, desto effektiver wird die darauf basierende Interpolationssuche, die aber bei unerwartet schlecht verteilten Einträgen wiederum zur Laufzeit der linearen Suche (O(n)) verkümmert. Diesem potentiellen Nachteil wird versucht mit der quadratischen Binärsuche zu begegnen, die wiederum eine Weiterentwicklung der Interpolationssuche ist. Und eben letztere würde ich auch versuchen wenn es um ziemlich viele Einträge geht. Bei nur ein paar hundert bis taused ist der Gewinn gegenüber der einfachen binären Suche vermutlich nicht mehr SO ausschlaggebend - je nach Anwendungsfall halt.

Wenn du recht genau weisst, dass deine Einträge z.B. grob quadradtisch oder logarithmisch vorkommen, könntest du durch Anpassung des Teilungsintervalls die einfache binäre Suche auch schon auf ein prima Niveau bekommen, aber das sind dann spezialisierte Anpassungen die ganz von der jeweils einzelnen Liste abhängen.