Arbeitsblatt Suchalgorithmen I
Lösung geprüft
Die Aufgabe der heutigen Stunde ist das Arbeitsblatt zu Suchalgorithmen I! Ein unsortiertes Array, die Zahl 64 soll gefunden werden. Die eigentliche Frage ist gar nicht, wie man sucht, sondern welches Verfahren hier überhaupt in Frage kommt – und warum die Antwort auf das unsortierte Array zurückgeht.
1 Einzelarbeit: In Material 1 finden Sie ein Array,
in welchem die Zahl 64 gesucht wird.
a) Begründen Sie, welches Suchverfahren Sie verwenden würden und wie
dieses vorgeht.
b) Nutzen Sie das von Ihnen gewählte Suchverfahren und führen Sie es
Schritt-für-Schritt durch. Nutzen Sie hierfür die Vorlage in
Material 2.
2 Einzelarbeit: Nun wird die Zahl 63 im Array gesucht. Beschreiben Sie, wie die lineare Suche hier vorgehen würde.
Material 1 – das Array
| Index | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Inhalt | 120 | 4 | 8 | 9 | 1 | 25 | 37 | 64 | 55 | 2 | 130 |
1 a) Welches Verfahren und warum
Hier kommt nur die lineare Suche in Frage, und der Grund steht direkt im Array: es ist unsortiert. Schau dir die Reihenfolge an – 120, dann 4, dann 8, dann 9, dann wieder 1. Da ist keine Ordnung drin.
Die binäre Suche würde in der Mitte anfangen, bei Index [5] mit dem Wert 25. Sie würde feststellen, dass 25 kleiner als 64 ist, und daraus schließen: „dann muss die 64 rechts davon liegen" – und die komplette linke Hälfte wegwerfen. Diese Schlussfolgerung ist aber nur bei sortierten Daten erlaubt. Hier stehen links Werte wie 120, die größer sind als 64. Die binäre Suche würde also zufällig manchmal etwas finden und manchmal nicht. Sie ist schlicht nicht anwendbar.
Wie die lineare Suche vorgeht: Sie fängt beim ersten Element an und vergleicht es mit dem Suchwert. Passt es nicht, geht sie ein Feld weiter. Das wiederholt sie, bis sie den Wert findet oder das Array zu Ende ist.
flowchart TD
A["gefunden = false, zaehler = 0"] --> B{"gefunden == false UND zaehler < Länge des Arrays?"}
B -- nein --> Z["return gefunden"]
B -- ja --> C{"aktuelles Element gleich Suchschlüssel?"}
C -- WAHR --> D["gefunden = true"]
C -- FALSCH --> E["zaehler = zaehler + 1"]
D --> E
E --> B
Im Struktogramm merkt sich die Suche das Ergebnis in einer Variablen
gefunden, und die steht mit in der Schleifenbedingung. Nach
einem Treffer wird der Zähler zwar noch einmal hochgezählt, aber beim
nächsten Prüfen der Bedingung ist Schluss – genauso wie dann, wenn der
Zähler hinten aus dem Array läuft. Im Java-Code weiter unten erledigt das
return dasselbe, nur eben sofort.
1 b) Schritt für Schritt nach der 64
| Durchlauf | geprüfter Index | Inhalt | = 64? |
|---|---|---|---|
| 1 | [0] | 120 | nein |
| 2 | [1] | 4 | nein |
| 3 | [2] | 8 | nein |
| 4 | [3] | 9 | nein |
| 5 | [4] | 1 | nein |
| 6 | [5] | 25 | nein |
| 7 | [6] | 37 | nein |
| 8 | [7] | 64 | ja → gefunden bei Index 7 |
8 Durchläufe. Die Suche hört sofort auf, wenn sie fündig wird – die Indizes [8], [9] und [10] schaut sie gar nicht mehr an. Das ist wichtig für die Aufgabe: die lineare Suche braucht höchstens n Vergleiche, nicht immer.
2 – Die Suche nach der 63
Die 63 steht nicht im Array. Die lineare Suche merkt das aber erst, wenn sie alle elf Felder geprüft hat – von [0] bis [10]. Erst wenn der Index über das Ende hinausläuft, steht fest: der Wert ist nicht da, Rückgabe „nicht gefunden".
| Fall | Vergleiche |
|---|---|
| Bester Fall – der Wert steht bei [0] | 1 |
| Durchschnitt – der Wert ist irgendwo drin | etwa n/2, hier rund 6 |
| Schlimmster Fall – der Wert steht ganz hinten oder ist gar nicht da | n, hier 11 |
Genau das ist der Punkt der Aufgabe: der Nicht-gefunden-Fall ist immer der schlimmste Fall. Bei einem gefundenen Wert kann man Glück haben, bei einem fehlenden nie. Man muss jedes einzelne Feld ausschließen.
Die lineare Suche in Java
/**
*
* Lineare Suche auf einem unsortierten Array
*
* @version 1.0 vom 14.09.2025
* @meininfokurs.cmrg.site
*/
public class LineareSuche {
private int[] daten = {120, 4, 8, 9, 1, 25, 37, 64, 55, 2, 130};
/**
* Sucht einen Wert der Reihe nach.
*
* @param suchwert der gesuchte Wert
* @return der Index, oder -1 wenn der Wert nicht vorkommt
*/
public int sucheLinear(int suchwert) {
for (int i = 0; i < daten.length; i++) {
if (daten[i] == suchwert) {
return i; // gefunden, sofort raus
}
}
return -1; // alles durch, nichts gefunden
}
public static void main(String[] args) {
LineareSuche s = new LineareSuche();
System.out.println("64 steht bei Index: " + s.sucheLinear(64));
System.out.println("63 steht bei Index: " + s.sucheLinear(63));
} // end of main
} // end of class LineareSucheZwei Sachen zur Umsetzung. Das return i; mitten in der
Schleife beendet die Methode sofort – deshalb hören wir bei Index 7 auf
und laufen nicht weiter. Und der Rückgabewert -1 für „nicht
gefunden" ist reine Konvention: es gibt keinen Index -1, also kann man den
Wert nicht mit einem echten Treffer verwechseln. Dieselbe Konvention
benutzt auch indexOf bei der ArrayList.
64 steht bei Index: 7
63 steht bei Index: -1