Binäre Suche: den Suchbereich halbieren

1. Die erste Mitte ist Index 3; ihr Wert 12 ist kleiner als 23.
2. Berechne die zweite Mitte aus den neuen Grenzen 4 und 6, nicht erneut aus 0 und 6.

Zuerst ist mitte=3 mit Wert 12; der neue Bereich lautet [4,6]. Danach ist mitte=5 mit Wert 23: Trefferindex 5 nach zwei Suchproben.

1. Der bereits geprüfte Mittelindex wird bei jedem Schritt ausgeschlossen.
2. Nach dem Wert 6 wird links zu 2; nach dem Wert 10 wird rechts zu 1.

mitte=1 liefert 6 < 7, also links=2. mitte=2 liefert 10 > 7, also rechts=1. Nun ist links=2 > rechts=1: Der Bereich ist leer.

1. // ist Ganzzahldivision: (0+5)//2 ergibt 2.
2. Nach rechts=1 ergibt (0+1)//2 den Index 0, nicht 1.

Im Bereich [0,5] ist die linke Mitte 2 mit Wert 6. Danach bleibt [0,1]; dessen linke Mitte 0 enthält bereits das Ziel 1. Besuchte Indizes: 2,0.

1. Solange links <= rechts gilt, enthält der Bereich noch mindestens eine Position.
2. Verwende mitte+1 bzw. mitte−1; ohne den Ausschluss der Mitte kann die Schleife stehen bleiben.

def binaer(a, ziel):
    links = 0
    rechts = len(a) - 1
    while links <= rechts:
        mitte = (links + rechts) // 2
        if a[mitte] == ziel:
            return mitte
        if a[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1
    return -1

1. Erhöhe proben einmal pro while-Durchlauf, unmittelbar bei der mittleren Probe.
2. Auch die letzte erfolglose Mittelprobe zählt; ein schon zu Beginn leerer Bereich hat dagegen 0 Proben.

def binaer_proben(a, ziel):
    links, rechts = 0, len(a) - 1
    proben = 0
    while links <= rechts:
        mitte = (links + rechts) // 2
        proben += 1
        if a[mitte] == ziel:
            return proben
        if a[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1
    return proben

1. Ein passender Mittelwert ist ein Kandidat, aber links davon könnte ein früherer passender Wert stehen.
2. Bei a[mitte] >= ziel merke mitte und setze rechts = mitte−1; bei kleinerem Wert gehe mit links = mitte+1 nach rechts.

def untere_grenze(a, ziel):
    links, rechts = 0, len(a) - 1
    kandidat = len(a)
    while links <= rechts:
        mitte = (links + rechts) // 2
        if a[mitte] >= ziel:
            kandidat = mitte
            rechts = mitte - 1
        else:
            links = mitte + 1
    return kandidat

1. Das Vergleichen der Mitte liefert nur mit bekannter Ordnung Informationen über andere Positionen.
2. Die Variante „untere Grenze“ sucht nach einem Treffer weiter links; die einfache Binärsuche tut das nicht.

Die Sortierung begründet den Ausschluss: Links vom zu kleinen Mittelwert können keine größeren Zielwerte liegen. Ohne Ordnung gilt das nicht; die einfache Variante verspricht bei Duplikaten keinen ersten Treffer.

1. Alle gelesenen Werte sind kleiner als 15, deshalb wandert jedes Mal die linke Grenze nach rechts.
2. Notiere die Bereiche [0,14], [8,14], [12,14] und [14,14].

Die besuchten Mittelindizes sind 7, 11, 13 und 14. Danach ist links=15 größer als rechts=14. Das sind vier Suchproben.