Beispiele für Aufgaben zur linearen und binären Suche

3.1 Aufgabe zum Finden eines Elements in einem Array mit linearer Suche

Aufgabe: Gegeben ist ein Array von Zahlen. Es ist der Index einer gegebenen Zahl mittels linearer Suche zu finden. Wenn die Zahl nicht gefunden wird, gib -1 zurück.

Beispiel:

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

# Beispiel der Verwendung:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} gefunden an Index {result}")  # Ausgabe: Element 7 gefunden an 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 an Index {result}")  # Ausgabe: Element 5 gefunden an Index -1

Erklärung:

• Die Funktion linear_search geht jedes Element des Arrays arr durch und vergleicht es mit target.
• Wird das Element gefunden, wird dessen Index zurückgegeben.
• Wenn alle Elemente geprüft wurden und der gesuchte Wert nicht gefunden wurde, gibt die Funktion -1 zurück.

Schrittweises Vorgehen:

1. Array [4, 2, 7, 1, 9, 3] und gesuchter Wert 7.
2. Beginn der Suche: Vergleiche das erste Element (4) mit 7 — stimmt nicht überein.
3. Weiter zum nächsten Element (2) — stimmt nicht überein.
4. Weiter zum nächsten Element (7) — stimmt überein.
5. Gib den Index 2 zurück.

3.2 Aufgabe zum Finden eines Elements in einem sortierten Array mit binärer Suche

Aufgabe: Gegeben ist ein sortiertes Array von Zahlen. Es ist der Index einer gegebenen Zahl mittels binärer Suche zu finden. Wenn die Zahl nicht gefunden wird, gib -1 zurück.

Beispiel:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Beispiel der Verwendung:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} gefunden an Index {result}")  # Ausgabe: Element 7 gefunden an Index 3

# Beispiel der Verwendung für ein Element, das nicht im Array ist:
target = 6
result = binary_search(sorted_array, target)
print(f"Element {target} gefunden an Index {result}")  # Ausgabe: Element 6 gefunden an Index -1

Erklärung:

• Die Funktion binary_search verwendet zwei Zeiger (left und right), um die Suchgrenzen im Array arr zu verfolgen.
• In jeder Iteration wird das mittlere Element des Arrays gefunden und mit target verglichen.
• Wenn das mittlere Element gleich target ist, wird dessen Index zurückgegeben.
• Wenn target kleiner als das mittlere Element ist, wird die Suche in der linken Hälfte des Arrays fortgesetzt.
• Wenn target größer als das mittlere Element ist, wird die Suche in der rechten Hälfte des Arrays fortgesetzt.
• Wenn die Grenzen sich überschneiden und das Element nicht gefunden wurde, wird -1 zurückgegeben.

Schrittweises Vorgehen:

1. Sortiertes Array [1, 3, 5, 7, 9, 11, 13] und gesuchter Wert 7.
2. Initiale Suchgrenzen: left = 0, right = 6.
3. Finde das mittlere Element: mid = (0 + 6) // 2 = 3.
4. Vergleiche das mittlere Element (7) mit target (7) — stimmt überein.
5. Gib den Index 3 zurück.

3.3 Vergleich und Auswahl des geeigneten Suchalgorithmus für verschiedene Aufgaben

Vergleich von linearer und binärer Suche:

Auswahl des geeigneten Algorithmus

Lineare Suche:

• Wird verwendet, wenn die Daten nicht sortiert sind.
• Geeignet für kleine Arrays oder Listen.
• Wird angewandt, wenn die Anzahl der Elemente klein ist und die Ausführungszeit nicht kritisch ist.

Binäre Suche:

• Wird angewandt, wenn die Daten sortiert sind.
• Ideal für große Arrays, wo die Suchgeschwindigkeit wichtig ist.
• Effizient, wenn häufige Suchen in demselben Datensatz erforderlich sind (die Daten können vorher sortiert werden).

3.4 Praktische Aufgaben zur Festigung des Materials

Aufgabe 1: Lineare Suche

Gegeben ist ein Array von Zahlen. Schreibe eine Funktion, um eine gegebene Zahl mittels linearer Suche zu finden. Die Funktion sollte den Index des gefundenen Elements oder -1 zurückgeben, wenn das Element nicht gefunden wurde.

Beispiel:

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

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

# Weitere Tests:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Aufgabe 2: Binäre Suche

Gegeben ist ein sortiertes Array von Zahlen. Schreibe eine Funktion, um eine gegebene Zahl mittels binärer Suche zu finden. Die Funktion sollte den Index des gefundenen Elements oder -1 zurückgeben, wenn das Element nicht gefunden wurde.

Beispiel:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Beispiel der Verwendung:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} gefunden an Index {result}")  # Ausgabe: Element 7 gefunden an Index 3

# Weitere Tests:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Aufgabe 3: Vergleich linearer und binärer Suche

Gegeben ist ein Array von Zahlen. Schreibe zwei Funktionen, um eine gegebene Zahl zu finden: eine mit linearer Suche, die andere mit binärer Suche. Vergleiche die Leistung beider Funktionen bei großen Arrays.

Beispiel:

import time
import random

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

# Binäre Suche
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Erzeugung eines großen Arrays
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Vergleich der Leistung
start_time = time.time()
linear_search(large_array, target)
print(f"Lineare Suche dauerte: {time.time() - start_time:.6f} Sekunden")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Binäre Suche dauerte: {time.time() - start_time:.6f} Sekunden")