Deutsch
Menü

Datenstrukturen und Algorithmen

Welche Voraussetzung muss erfüllt sein, um die binäre Suche zu verwenden, die den Zielwert mit dem mittleren Element vergleicht und den Suchbereich jedes Mal halbiert?

  1. ADie Zahl der Datenelemente muss eine Zweierpotenz sein
  2. BDie Daten müssen nach dem Schlüssel sortiert sein
  3. CDie Daten dürfen keine doppelten Werte enthalten
Antwort und Erläuterung anzeigen

Antwort: B. Die Daten müssen nach dem Schlüssel sortiert sein

Die binäre Suche entscheidet anhand des Vergleichs mit dem mittleren Element, ob der Zielwert in der vorderen oder hinteren Hälfte liegt, und halbiert den Bereich. Dieser Schluss gilt nur, weil die Daten sortiert sind; auf ein unsortiertes Array lässt sich die binäre Suche nicht anwenden. Die Zahl der Elemente muss keine Zweierpotenz sein; wählt man die Mitte zum Beispiel als (untere Grenze + obere Grenze) ÷ 2 abgerundet, funktioniert sie bei jeder Größe. Doppelte Werte sind ebenfalls kein Problem: Einer der passenden Werte wird gefunden (um das erste Vorkommen zu finden, ist ein kleiner Zusatzschritt nötig).

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. 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?
  2. 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?
  3. 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?
  4. 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?
  5. 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?