Arrays in Python - Binäre Suche

Druchsucht man ein Array Element für Element braucht man n Vergleiche, bei einer Arraylänge von n.
Dies kann sehr aufwendig sein, wenn die Arrays sehr lang sind. Z.B. bei der Suche einer Person in Deutschland wären über 80 Millionen Vergleiche nötig, beim Suchen einer Bestellung eines Händlers mehrere Milliarden (große Onlinehändler verschicken über 4 Mrd. Pakete pro Jahr) oder bei Aktienhandel.

Bei der Binären Suche nimmt man das mittlere Element des Arrays und vergleicht es mit dem gesuchten Wert.

• ist das mittlere Element der gesuchte Wert, hat man ihn gefunden und endet
• ist das mittlere Element kleiner als der gesuchte Wert, sucht man in der oberen Hälfte weiter
• ist das mittlere Element größer als der gesuchte Wert, sucht man in der unteren Hälfte weiter

Dies wiederholt man bis die obere und untere Grenze gleich sind (oder die obere Grenze kleiner als die untere Grenze ist).
Da das mittlere Element bereits verglichen wurde, kann der Bereich sogar noch eins kleiner gemacht werden.

def binSuche(feld, gesucht):
    untereGrenze = 0
    obereGrenze = len(feld)-1
    
    while untereGrenze <= obereGrenze:
        mitte = (obereGrenze+untereGrenze)//2
        if feld[mitte] == gesucht:
            return True
        elif feld[mitte]<gesucht:
            untereGrenze = mitte+1
        else:
            obereGrenze = mitte-1
    return False