Themenbereich 6: Binäre Suchalgorithmen untersuchen und erklären

Question 1

Was versteht man in der Informatik unter der „binären Suche“?

Answer 1

Die Daten müssen bei der Binären Suche sortiert vorliegen, nur dann ist eine Durchführung möglich. Das heißt, man teilt die zu durchsuchenden Daten in zwei Hälften und ermittelt dann, in welcher Hälfte das zu suchende Element vorkommt. Die andere Hälfte kann ignoriert werden. So wird bereits im ersten Suchschritt, die Menge der zu durchsuchenden Daten um 50% reduziert. Dieser Schritt wiederholt sich, bis ein Treffer
erzielt wird.

Question 2

Erläutern Sie den angeführten Suchalgorithmus am Beispiel des Suchens der Zahl 54 im Bereich der Zahlenmenge von 100 ganzzahligen Werten.

static void binaerSuche(int[] feld, int links,int rechts, int kandidat) {int mitte; do{

System.out.println(“Intervall [” + links +”,” + rechts + “]”);

mitte = (rechts + links) / 2; if(feld[mitte] < kandidat){ links = mitte + 1;} else { rechts = mitte - 1;

Answer 2

Dieser angegebene Suchalgorithmus ist ein Beispiel für die binäre Suche. Die binäre Suche ist ein effizienter Suchalgorithmus, der auf einer sortierten Liste von Elementen arbeitet. Hier ist eine Erläuterung des Algorithmus und wie er auf das Suchen der Zahl 54 im Bereich einer
Zahlenmenge von 100 ganzzahligen Werten angewendet werden könnte:

1. Sortierung des Arrays: Bevor die binäre Suche angewendet wird, muss das Array sortiert werden, da die binäre Suche nur auf sortierten Arrays funktioniert.
2. Algorithmusübersicht: Der Algorithmus beginnt mit einem Intervall, das den gesamten Bereich der Liste abdeckt (in diesem Fall 100 Elemente). Dann wird das Intervall schrittweise halbiert, indem die Mitte des aktuellen Intervalls berechnet wird. Wenn der Wert an der Mitte des Intervalls kleiner als der gesuchte Wert ist, wird das Intervall auf die rechte Hälfte des aktuellen Intervalls reduziert. Wenn der Wert an der
   Mitte des Intervalls größer als der gesuchte Wert ist, wird das Intervall auf die linke Hälfte des aktuellen Intervalls reduziert. Dieser Prozess wird fortgesetzt, bis der gesuchte Wert gefunden wird oder das Intervall leer ist.
3. Beispiel: Angenommen, das sortierte Array sieht folgendermaßen aus: [1, 4, 7, 11, …, 97, 99]. Zuerst wird das Intervall auf den gesamten Bereich der Liste gesetzt: [0, 99].
   Dann wird die Mitte des Intervalls berechnet, was 49 ist. Der Wert an Index 49 im Array ist 50, was kleiner als 54 ist, daher wird das Intervall auf [50, 99] reduziert. Dann wird die Mitte des neuen Intervalls berechnet, was 74 ist. Der Wert an Index 74
   im Array ist 75, was größer als 54 ist, daher wird das Intervall auf [50, 73] reduziert. Dieser Prozess wird fortgesetzt, bis entweder der gesuchte Wert gefunden wird oder
   das Intervall leer ist.

In diesem Pseudocode sucht die Funktion binaerSuche nach dem Wert kandidat im Bereich zwischen den Indizes links und rechts im Array feld. Der Algorithmus aktualisiert kontinuierlich das Intervall basierend auf dem Vergleich zwischen dem Wert an der Mitte des Intervalls und dem gesuchten Wert, bis entweder der Wert gefunden wird oder
das Intervall leer ist.

Question 3

Was versteht man in der Informatik unter der „linearen Suche“?

Answer 3

Die Lineare Suche wird verwendet um in einer unsortierten Zeichenkette ein gesuchte(s)
Zeichen/Zeichenkette zu finden. Es ist der einfachste Suchalgorithmus und ist auch unter sequentielle Suche bekannt. Hier wird Zeichen (Stelle) für Zeichen (Stelle) der Reihe nach
verglichen, gibt es eine Übereinstimmung wird die Position an dem sich das Zeichen befindet
zurückgegeben. Die Suchdauer steigt proportional zur durchsuchenden Zeichenkette an.

Question 4

Erläutern Sie den angeführten Suchalgorithmus in der Sprache JAVA in allgemeinen Worten

public static int lineareSuche(final int gesucht, final int[] daten) {for (int i = 0; i < daten.length;
i++) {if (daten[i] == gesucht) {return i; }} return -1;}

Answer 4

Dieser angegebene Suchalgorithmus ist eine Implementierung der linearen Suche in Java. Die lineare Suche ist eine einfache Suchmethode, bei der jedes Element in der Liste nacheinander überprüft wird, bis das gesuchte Element gefunden wird oder das Ende der Liste erreicht ist.

Durchlaufen des Arrays: Der Algorithmus durchläuft das gesamte Array daten von Anfang bis Ende, beginnend mit dem Index 0 bis zum letzten Index daten. - length - 1.

Vergleichen der Werte: Bei jedem Schritt wird das aktuelle Element des Arrays mit dem gesuchten Wert -gesucht - verglichen. Wenn das aktuelle Element gleich dem gesuchten Wert ist, wird der Index dieses Elements zurückgegeben, was bedeutet, dass das gesuchte Element
gefunden wurde.

Rückgabewert bei Erfolg: Wenn das gesuchte Element gefunden wird, wird der Index dieses Elements zurückgegeben. Dies ist der Ort, an dem das Element im Array gefunden wurde.

Rückgabewert bei Misserfolg: Wenn das gesuchte Element nicht gefunden wird, wird -1 zurückgegeben, um anzuzeigen, dass das Element nicht im Array vorhanden ist.

In diesem Algorithmus wird jedes Element in daten nacheinander überprüft, um zu sehen, ob es mit dem gesuchten Wert übereinstimmt. Wenn eine Übereinstimmung gefunden wird, wird der Index dieses Elements zurückgegeben. Wenn keine Übereinstimmung gefunden
wird, wird -1 zurückgegeben, um anzuzeigen, dass das gesuchte Element nicht im Array vorhanden ist.