Deutsch
Menü

Datenstrukturen und Algorithmen

Auf 1000 verschiedene, aufsteigend sortierte Werte wird eine binäre Suche angewendet. Ein Vergleich liefert jeweils „gleich“, „kleiner“ oder „größer“. Wie viele Vergleiche sind höchstens nötig, erfolgreiche und erfolglose Suchen zusammengenommen?

  1. A10
  2. B32
  3. C500
Antwort und Erläuterung anzeigen

Antwort: A. 10

Jeder Vergleich halbiert den Suchbereich ungefähr, und es gilt 2¹⁰ = 1024 ≥ 1000; nach höchstens 10 Vergleichen ist der Bereich also erschöpft (⌊log₂ 1000⌋ + 1 = 10). Die Komplexität ist O(log n), und selbst bei 1 Million Werten genügen höchstens 20 Vergleiche. 32 entspricht √1000 ≈ 31,6, und 500 liegt nahe am Mittelwert einer linearen Suche (etwa n/2). Zu beachten ist allerdings, dass die binäre Suche sortierte Daten braucht und das Sortieren selbst O(n log n) kostet.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Eine binäre Suche sucht 38 im aufsteigend sortierten Array a[0] bis a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Der Suchbereich beginnt mit lo = 0 und hi = 9, und die mittlere Position ist (lo + hi) ÷ 2 abgerundet. Welche Folge gibt die Elemente, die mit 38 verglichen werden, in der richtigen Reihenfolge an?
  2. Das Array 5, 3, 8, 1, 4 wird mit Bubblesort aufsteigend sortiert. Wie sieht das Array nach einem Durchlauf aus, bei dem benachbarte Elemente von vorn bis zum Ende verglichen und vertauscht werden, wenn das linke größer ist?
  3. Das Array 29, 10, 14, 37, 13 wird mit Selectionsort aufsteigend sortiert: Das Minimum des unsortierten Teils wird gesucht und mit dem ersten Element des unsortierten Teils vertauscht. Wie sieht das Array aus, nachdem dieser Schritt zweimal ausgeführt wurde?
  4. Ein Array mit 10 Elementen wird mit Insertionsort aufsteigend sortiert. Jedes Element ab dem zweiten wird herausgenommen und mit den Elementen links davon verglichen, beginnend beim linken Nachbarn, bis ein Element gefunden wird, das kleiner oder gleich ist, oder der Anfang erreicht ist. Wie viele Vergleiche sind nötig, wenn das Array bereits aufsteigend sortiert ist, und wie viele, wenn es absteigend sortiert ist?
  5. Welches Sortierverfahren hat auch im schlechtesten Fall die Komplexität O(n log n) und sortiert fast ohne zusätzlichen Speicher wie ein Arbeitsarray?