Binärer Python-Suchalgorithmus

Durchsuchen Sie sortierte Listen in logarithmischer O(log n)-Zeit. Führen Sie die binäre Suche in Python aus und verstehen Sie sie, einschließlich Schritt-für-Schritt-Logik, Randfällen und Optimierungen.

Versuchen Sie es im Editor

Übersicht

Die binäre Suche ist ein äußerst effizienter Algorithmus zum Auffinden eines Elements in einer sortierten Liste. Im Gegensatz zur linearen Suche, bei der jedes Element nacheinander in O(n)-Zeiten durchsucht wird, funktioniert die binäre Suche durch wiederholtes Teilen des Suchintervalls in zwei Hälften.

Die Suche beginnt mit der Untersuchung des mittleren Elements des Arrays. Wenn der Zielwert mit dem mittleren Element übereinstimmt, wird dessen Position zurückgegeben. Wenn das Ziel kleiner ist, beschränkt der Algorithmus seine Suche auf die untere Hälfte; Wenn das Ziel größer ist, wird es auf die obere Hälfte eingegrenzt. Dieser Vorgang wiederholt sich, bis das Element gefunden wird oder die Subarray-Größe auf Null sinkt.

Um die binäre Suche in Python zu implementieren, verwenden wir zwei Zeiger (niedrig und hoch), um die aktiven Suchgrenzen zu verfolgen. Da der Suchraum bei jedem Schritt um die Hälfte kleiner wird, wird der Algorithmus in O(log n)-Zeit ausgeführt, was ihn ideal für große Datenbanken macht.

Code- und Ausführungsausgabe

Eine standardmäßige iterative binäre Suchimplementierung, die den Index eines Zielelements in einer sortierten Liste zurückgibt.

binary_search.py

Versuchen Sie es im Editor

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

Terminal-Ausgabe

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

Schrittweise Umsetzung

Abfrageindizierung und Suche in Datenbanktabellen
Finden von Schwellen- oder Grenzwerten in kontinuierlichen mathematischen Bereichen
Autovervollständigung und Suchfunktionen in Textfeldern

Häufig gestellte Fragen

Muss die Liste sortiert sein, damit die binäre Suche funktioniert?

Ja, die binäre Suche basiert ausschließlich auf der Sortierung der Elemente. Wenn die Liste unsortiert ist, bricht die Vergleichslogik zusammen und Sie müssen die Liste zuerst sortieren oder eine lineare Suche verwenden.

Warum die iterative Binärsuche anstelle der rekursiven Binärsuche verwenden?

Während die rekursive binäre Suche elegant ist, wird in der Produktion oft die iterative binäre Suche bevorzugt. Der iterative Ansatz läuft im O(1)-Hilfsraum, während die rekursive Suche aufgrund des Aufrufstapels O(log n)-Raum beansprucht, was bei extrem großen Eingaben zu einem Stapelüberlauf führt.