Lineare Suche

1.1 Definition der linearen Suche

Lineare Suche (auch bekannt als sequenzielle Suche) ist ein Algorithmus zur Suche eines Elements in einer Liste oder einem Array, der jedes Element nacheinander überprüft, bis es eine Übereinstimmung findet oder alle Elemente überprüft sind. Es ist der einfachste Suchalgorithmus, der keine vorherige Sortierung der Daten erfordert.

Grundprinzipien:

• Sequentielle Überprüfung: Der Algorithmus geht durch jedes Element des Arrays oder der Liste und vergleicht es mit dem gesuchten Wert.
• Beendigung der Suche: Die Suche endet, wenn ein Element gefunden wird, das dem gesuchten Wert entspricht, oder alle Elemente überprüft wurden.
• Keine Sortierung erforderlich: Die lineare Suche kann auf unsortierte Daten angewendet werden.
• Anwendung: Die lineare Suche kann auf alle Datenstrukturen angewendet werden, die eine Iteration unterstützen, einschließlich Listen und Arrays.

Die lineare Suche hat eine Zeitkomplexität von O(n), wobei n die Anzahl der Elemente im Array oder in der Liste ist. Im schlimmsten Fall muss der Algorithmus alle n Elemente überprüfen, um den gesuchten Wert zu finden oder dessen Fehlen zu bestimmen.

Analyse der Zeitkomplexität:

• Bester Fall (Best case): Das Element wird an der ersten Stelle gefunden, O(1).
• Durchschnittlicher Fall (Average case): Das Element wird irgendwo in der Mitte gefunden, O(n/2), was äquivalent zu O(n) ist.
• Schlimmster Fall (Worst case): Das Element wird an der letzten Stelle oder gar nicht gefunden, O(n).

1.2 Schrittweise Implementierung der linearen Suche

Schritte der linearen Suche:

• Initialisierung: Setze den Startindex für die Suche fest (normalerweise der Nullindex).
• Sequentielle Überprüfung: Überprüfe jedes Element der Liste oder des Arrays auf Übereinstimmung mit dem gesuchten Wert.
• Abbruchbedingung: Wenn das Element gefunden wird, gib dessen Index zurück. Wenn alle Elemente überprüft wurden und der gesuchte Wert nicht gefunden wurde, gib einen speziellen Wert zurück (normalerweise -1 oder None).

Implementierung der linearen Suche in Python:

def linear_search(arr, target):
    # Gehe durch jedes Element des Arrays
    for index, element in enumerate(arr):
        # Wenn das aktuelle Element dem gesuchten Wert entspricht, gib dessen Index zurück
        if element == target:
            return index
    # Wenn das Element nicht gefunden wird, gib -1 zurück
    return -1

Schrittweise Erklärung der Implementierung:

• Initialisierung der Schleife: Eine for-Schleife wird zusammen mit der Funktion enumerate verwendet, die den Index und das Element des Arrays in jeder Iteration zurückgibt.
• Vergleich: In jeder Iteration wird das aktuelle Element mit dem gesuchten Wert (target) verglichen.
• Rückgabe des Indexes: Wenn das aktuelle Element dem gesuchten Wert entspricht, wird der Index dieses Elements zurückgegeben.
• Rückgabe von -1: Wenn die Schleife abgeschlossen ist und das gesuchte Element nicht gefunden wurde, wird -1 zurückgegeben.

# Beispiel der Verwendung:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} gefunden bei Index {result}")  # Ausgabe: Element 7 gefunden bei Index 2

# Beispiel der Verwendung für ein Element, das nicht im Array ist:
target = 5
result = linear_search(arr, target)
print(f"Element {target} gefunden bei Index {result}")  # Ausgabe: Element 5 gefunden bei Index -1

1.3 Aufgabenbeispiele, die mit linearer Suche gelöst werden

Die lineare Suche wird verwendet, um eine Vielzahl von Aufgaben zu lösen, die mit der Suche von Elementen in Datensammlungen zusammenhängen. Hier sind einige Beispiele solcher Aufgaben:

Aufgabe 1: Suche eines Elements im Array

Ein bestimmtes Zahl muss in einem Array von Zahlen gefunden werden.

Beispiel:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Element {target} gefunden bei Index {index}")  # Ausgabe: Element 70 gefunden bei Index 3

Aufgabe 2: Prüfung auf die Anwesenheit eines Elements in der Liste

Es muss geprüft werden, ob ein bestimmter Wert in der Liste von Strings vorhanden ist.

Beispiel:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Element {target} {'gefunden' if found else 'nicht gefunden'}")  # Ausgabe: Element cherry gefunden

Aufgabe 3: Suche nach dem minimalen oder maximalen Element

Es muss der minimale oder maximale Wert in der Liste gefunden werden.

Beispiel:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Minimalwert: {min_value}")  # Ausgabe: Minimalwert: 2

Aufgabe 4: Suche nach dem ersten Vorkommen

Finde das erste Vorkommen eines bestimmten Elements in der Liste.

Beispiel:

def find_first_occurrence(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Erstes Vorkommen von {target} bei Index {index}")  # Ausgabe: Erstes Vorkommen von 2 bei Index 1

Aufgabe 5: Zählen der Vorkommen

Zähle die Anzahl der Vorkommen eines bestimmten Elements in der Liste.

Beispiel:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Element {target} kommt {count} mal vor")  # Ausgabe: Element 2 kommt 3 mal vor