Binäre Suche in Python

von

Wie bei der linearen Suche, geht es auch bei der binären Suche darum einen Wert in einer Liste zu finden, die in diesem Beispiel wie folgt aussieht:

MY_LIST = [4, 43, 12, 89, 17, 23, 1, 66, 103]

Zunächst ist es erforderlich, die Werte in der Liste zu ordnen, wofür die Methode sort() verwendet wird:

MY_LIST.sort()
print(MY_LIST)  # -> [1, 4, 12, 17, 23, 43, 66, 89, 103]

Die weitere Vorgehensweise sieht nun so aus, dass die Liste in der Hälfte geteilt wird. Hierfür wird jenes Element ermittelt, das sich in der Mitte befindet. Dies führt dann zu drei Möglichkeiten:

  1. Das gesuchte Element entspricht dem ermittelten “Mitte-Element”.
  2. Das gesuchte Element befindet sich in der ersten Hälfte der Liste.
  3. Das gesuchte Element befindet sich in der zweiten Hälfte der Liste.

Entspricht das gesuchte Element dem “Mitte-Element”, ist die Suche beendet. Andernfalls wird nur noch jene Hälfte weiter durchsucht, in dem sich das Element befinden muss. Mit jedem weiteren Suchlauf wird also eine Hälfte der Liste “eliminiert”.

Als Code sieht dies folgendermaßen aus:

def binary_search(number_list, number):
    """A binary search function

    Arguments:
        number_list {list} -- A list with sorted integer values
        number {integer} -- The number we are searching for

    Returns:
        integer -- Returns the index of the given number
    """
    lower_bound = 0
    upper_bound = len(MY_LIST)

    while lower_bound < upper_bound:
        mid_index = (lower_bound + upper_bound) // 2
        mid_index = int(mid_index)

        if number_list[mid_index] == number:
            return mid_index
        elif number_list[mid_index] < number:
            lower_bound = mid_index + 1
        else:
            upper_bound = mid_index

index_value = binary_search(MY_LIST, 89)
print(index_value)  # -> Index 7

Gesucht wird hier der Wert “89”:

index_value = binary_search(MY_LIST, 89)

Interessant wird es dann in der while-Schleife. Hier wird zunächst der aktuelle mid_index (bzw. der entsprechende Wert) bestimmt (hier: 23). Die darauf folgende if-Verzweigung erledigt die übrige Arbeit. Als erstes wird jener Fall erfasst, bei dem sich der gesuchte Wert am mid_index befindet:

if number_list[mid_index] == number:
    return mid_index

Dann wird überprüft, ob der Wert am mid_index kleiner ist als der gesuchte Wert:

elif number_list[mid_index] < number:
            lower_bound = mid_index + 1

Dies ist hier der Fall (23 < 89). Folglich kann sich der gesuchte Wert nur in der zweiten Hälfte befinden. Die untere Begrenzung dieser zweiten Hälfte ist dann:

lower_bound = mid_index + 1

Andernfalls würde mit

upper_bound = mid_index

der Mitte-Index als obere Begrenzung festgelegt werden. Oder anders ausgedrückt: Die zweit Hälfte würde nicht mehr berücksichtigt werden, und die nächste Suche würde lediglich in der ersten Hälfte der Liste erfolgen.

Im Gegensatz zu einer linearen Suche, wird bei der binären Suche nicht jedes Element überprüft. Stattdessen wird durch das Halbieren der Liste, die zu durchsuchende Menge stets reduziert. Im schlimmsten Fall bedeutet dies eine log-n-Iteration. Gemäß der Big-O-Notation liegt also ein O(log n)-Wert vor, was schneller ist als bei Anwendung einer linearen Suche, die eine Performance von O(n) hat.

Zuletzt aktualisiert am 15. September 2021