Algorithmische Suchaufgaben

9.1 Beispiele für Probleme, die durch lineare und binäre Suche gelöst werden

Lineare Suche

Aufgabe zur Suche eines Elements in einem Array: Gegeben ist ein Array von Zahlen und ein Zielwert. Es muss der Index des Zielwerts im Array gefunden werden.

Lösung: Wir verwenden die lineare Suche, um jedes Element des Arrays zu überprüfen.

Beispielimplementierung:

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

# Beispielverwendung:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Ausgabe: 2

Binäre Suche

Aufgabe zur Suche eines Elements in einem sortierten Array: Gegeben ist ein sortiertes Array von Zahlen und ein Zielwert. Es muss der Index des Zielwerts im Array gefunden werden.

Lösung: Wir verwenden die binäre Suche, um das Array zu halbieren und den Zielwert zu suchen.

Beispielimplementierung:

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

# Beispielverwendung:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Ausgabe: 3

9.2 Aufgaben zur Nutzung von Hash-Tabellen zur Optimierung der Suche

1. Suche nach Duplikaten im Array

Aufgabe: Gegeben ist ein Array von Zahlen. Finde und gib alle Duplikate im Array zurück.

Lösung: Wir verwenden eine Hash-Tabelle, um die bereits gesehenen Zahlen zu verfolgen. Wenn eine Zahl erneut auftaucht, fügen wir sie der Liste der Duplikate hinzu.

Beispielimplementierung:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Beispielverwendung
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Ausgabe: [2, 4]

2. Finden von Paaren mit einer gegebenen Summe

Aufgabe: Gegeben ist ein Array von Zahlen und ein Zielwert der Summe. Finde alle Paare von Zahlen, die zusammen den Zielwert ergeben.

Lösung: Wir verwenden eine Hash-Tabelle, um die Zahlen zu speichern und zu überprüfen, ob sie mit der aktuellen Zahl ein Paar bilden, das die Zielsumme ergibt.

Beispielimplementierung:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Beispielverwendung
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Ausgabe: [(1, 5), (7, -1), (1, 5)]

9.3 Kombinierte Nutzung verschiedener Suchmethoden

Bei komplizierten Aufgaben ist es oft nötig, mehrere Suchmethoden zu verwenden, um die beste Effizienz zu erzielen. Die kombinierte Nutzung von linearer Suche, binärer Suche und Hash-Tabellen ermöglicht es, Aufgaben effizienter und flexibler zu lösen.

Beispiel 1: Suche eines Elements im Array und Überprüfung seiner Existenz in einem anderen Array

Es sind zwei Arrays von Zahlen gegeben. Finde die Elemente des ersten Arrays, die im zweiten Array existieren.

Lösung:

• Verwende eine Hash-Tabelle, um die Elemente des zweiten Arrays zu speichern.
• Überprüfe für jedes Element des ersten Arrays dessen Existenz in der Hash-Tabelle.

Beispielimplementierung:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # Hash-Tabelle für das zweite Array
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# Beispielverwendung:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Ausgabe: [3, 4, 5]

Beispiel 2: Überprüfung, ob ein Subarray ein Anagramm-Array ist, mit Nutzung einer Hash-Tabelle

Gegeben ist ein Array von Strings und ein Muster-String. Überprüfe, ob ein beliebiges Subarray des Arrays ein Anagramm des Musters ist.

Lösung:

• Verwende eine Hash-Tabelle, um die Häufigkeit der Zeichen im Muster zu zählen.
• Gehe durch das Array von Strings und verwende ein „gleitendes Fenster“, um jedes Subarray auf die Entsprechung der Zeichenzählung zu überprüfen.

Beispielimplementierung:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# Beispielverwendung:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Ausgabe: True

9.4 Praktische Aufgaben zur Festigung des Materials

Aufgabe 1: Suche eines Elements in einem unsortierten Array

Gegeben ist ein Array von Zahlen und ein Zielwert. Finde den Index des Zielwerts im Array. Verwende die lineare Suche.

Beispiel:

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

# Beispielverwendung:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Ausgabe: 2

Aufgabe 2: Suche nach Duplikaten im Array

Gegeben ist ein Array von Zahlen. Finde und gib alle Duplikate im Array mit Nutzung einer Hash-Tabelle zurück.

Beispiel:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Beispielverwendung:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # Ausgabe: [3, 1]