4.1 Vergleich der zeitlichen Komplexität von linearer und binärer Suche
Lass uns die zeitliche Komplexität von linearer und binärer Suche vergleichen.
Lineare Suche:
- Zeitkomplexität:
O(n), wobeindie Anzahl der Elemente im Array oder in der Liste ist. - Best-Case:
O(1)— Element wird an erster Stelle gefunden. - Durchschnittsfall:
O(n/2) = O(n)— Element wird durchschnittlich in der Mitte gefunden. - Schlimmster Fall:
O(n)— Element wird an letzter Stelle gefunden oder fehlt.
Binäre Suche:
- Zeitkomplexität:
O(log n), wobeindie Anzahl der Elemente im Array oder in der Liste ist. - Best-Case:
O(1)— Element wird im ersten Schritt gefunden (mittleres Element). - Durchschnittsfall:
O(log n)— Suche in einem sortierten Array. - Schlimmster Fall:
O(log n)— Element wird im letzten Schritt gefunden oder fehlt.
Beispiel für die Analyse der Zeitkomplexität
Lineare Suche:
- Array
[1, 3, 5, 7, 9, 11, 13], gesuchtes Element 7. - Überprüfung jedes Elements bis 7 an Index 3 gefunden wird.
- 4 Überprüfungen erforderlich, was
O(n)entspricht.
Binäre Suche:
- Array
[1, 3, 5, 7, 9, 11, 13], gesuchtes Element7. - Mittleres Element (7) im ersten Schritt gefunden.
- 1 Überprüfung erforderlich, was
O(log n)entspricht.
4.2 Vor- und Nachteile jedes Verfahrens
Schauen wir uns die Vor- und Nachteile jedes Suchverfahrens an.
Lineare Suche:
Vorteile:
- Einfach zu implementieren: Lineare Suche ist sehr einfach zu implementieren und zu verstehen.
- Keine Anforderungen an die Daten: Lineare Suche kann für unsortierte Daten verwendet werden.
- Geeignet für kleine Arrays: Lineare Suche ist effizient für Arrays kleiner Größe.
Nachteile:
- Geringe Effizienz bei großen Arrays: Die Zeitkomplexität
O(n)macht sie bei großen Arrays ineffizient. - Lange Ausführungszeit: Für große Arrays kann die lineare Suche viel Zeit in Anspruch nehmen, insbesondere wenn das gesuchte Element näher am Ende des Arrays oder nicht vorhanden ist.
Binäre Suche:
Vorteile:
- Hohe Effizienz bei großen Arrays: Die Zeitkomplexität
O(log n)macht sie sehr effizient für große Arrays. - Schnelle Ausführung: Die binäre Suche ist erheblich schneller als die lineare Suche, wenn mit großen sortierten Arrays gearbeitet wird.
Nachteile:
- Sortierte Daten erforderlich: Die binäre Suche funktioniert nur mit sortierten Arrays, was zusätzliche Zeit für die Vorsortierung erfordern kann.
- Komplexität der Implementierung: Die Implementierung der binären Suche ist im Vergleich zur linearen Suche komplizierter.
4.3 Wann welchen Suchalgorithmus verwenden
Schauen wir uns an, wann man lineare Suche und wann binäre Suche verwenden sollte.
Lineare Suche.
Verwende lineare Suche, wenn:
- Das Array oder die Liste ist nicht sortiert.
- Die Größe des Arrays oder der Liste ist klein.
- Einfachheit und schnelle Lösung erforderlich sind, ohne zusätzliche Sortierkosten.
- Das erste Vorkommen oder alle Vorkommen eines Elements gefunden werden müssen.
- Daten in Echtzeit eintreffen und deren Vorsortierung unmöglich oder unpraktisch ist.
Binäre Suche.
Verwende binäre Suche, wenn:
- Das Array oder die Liste ist sortiert.
- Die Größe des Arrays oder der Liste ist groß.
- Häufige Suche von Elementen in demselben Datensatz (Daten können einmalig vorsortiert werden).
- Hohe Suchgeschwindigkeit wichtig ist.
- Es akzeptabel ist, Zeit für die Vorsortierung der Daten zu verwenden.
4.4 Beispiele für Aufgaben zur linearen Suche
1. Suche in einer unsortierten Liste
Finde den Index einer gegebenen Zahl in einer unsortierten Liste von Zahlen.
Beispiel:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target)) # Ausgabe: 2
2. Suche nach dem ersten Vorkommen in einem Array
Finde das erste Vorkommen eines gegebenen Elements in einer Liste von Strings.
Beispiel:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target)) # Ausgabe: 1
3. Suche in Echtzeitdaten
Finde ein Element in einem Echtzeit-Datenstrom.
Beispiel:
import random
def find_in_stream(stream, target):
for index, element in enumerate(stream):
if element == target:
return index
return -1
stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))
4.5 Beispiele für Aufgaben zur binären Suche
1. Suche in einem sortierten Array
Finde den Index einer gegebenen Zahl in einem sortierten Array von Zahlen.
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
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target)) # Ausgabe: 3
2. Häufige Suche in einem großen Datensatz
Häufige Suche von Elementen in einem großen sortierten Array von Zahlen.
Beispiel:
import random
sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))
3. Suche nach einem Element in einer sortierten Datenbank
Finde einen Eintrag in einer sortierten Datenbank basierend auf einem Schlüsselwert.
Beispiel:
database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
left, right = 0, len(db) - 1
while left <= right:
mid = (left + right) // 2
if db[mid]["id"] == target_id:
return db[mid]
elif db[mid]["id"] < target_id:
left = mid + 1
else:
right = mid - 1
return None
target_id = 54321
print(binary_search_db(database, target_id))
GO TO FULL VERSION