Algorithmen
Such-Vergleich
Lineare und binäre Suche live nebeneinander. Bei welchem n lohnt sich der Aufwand des Sortierens? Wann ist Linear schneller? Klausur-Übersicht.
3LerneinheitenVoraussetzungen:Lineare SucheBinäre Suche
Sprache wählen
Sprache
Lerneinheit 1 von 3
Linear vs Binär im Vergleich
Du kennst beide Verfahren. Hier siehst du sie nebeneinander, sowohl in der Theorie als auch (im nächsten Tab) live in der Animation.
Übersicht
| Algorithmus | Worst Case | Average Case | Best Case | Voraussetzung |
|---|---|---|---|---|
| Lineare Suche | O(n) | O(n) | O(1) | Keine |
| Binäre Suche | O(log n) | O(log n) | O(1) | Sortiert |
Der Unterschied in Zahlen
| n | Linear | Binär | Faktor |
|---|---|---|---|
| 100 | 100 | 7 | 14× |
| 1.000 | 1.000 | 10 | 100× |
| 1.000.000 | 1.000.000 | 20 | 50.000× |
| 1 Milliarde | 1 Mrd. | 30 | 33 Mio× |
Bei großen Daten ist Binär ungeschlagen.
Wann welcher?
- Lineare Suche:
- Bei kleinen Arrays (n < 100)
- Bei unsortierten Daten ohne Sortier-Möglichkeit
- Bei einmaligen Suchen, wo der Sortier-Aufwand sich nicht lohnt
- Binäre Suche:
- Bei großen sortierten Arrays
- Bei vielen wiederholten Suchen auf demselben Array
- Bei Datenbank-Indizes (intern via B-Bäume)
Was Bibliotheken machen
- Java:
Arrays.binarySearch()undCollections.binarySearch() - Python:
bisectModul (bisect_left,bisect_right) - C++:
std::binary_searchundstd::lower_bound
Aber im Kopf haben muss man beide, sie tauchen in jeder Algorithmik-Klausur auf.
Weiter im Tab "Interaktiv" siehst du beide Algorithmen live nebeneinander.