Wie funktioniert die binäre Suche in einer sortierten Liste?

Binäre Suche ist ein Algorithmus zur Suche eines Elements in einer sortierten Liste mit einer logarithmischen Komplexität von O(log n). Er arbeitet nach dem Prinzip "Teile und Herrsche":

1. Das mittlere Element der Liste wird bestimmt.
2. Wenn das gesuchte Element gleich dem Mittel ist, endet die Suche.
3. Wenn das gesuchte Element kleiner als das Mittel ist, wird die Suche im linken Teil der Liste fortgesetzt.
4. Wenn es größer ist, im rechten Teil.

Der Prozess wird rekursiv oder iterativ wiederholt, bis das Element gefunden wird oder der Suchbereich erschöpft ist.

Beispiel in Go:

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // Element nicht gefunden
}