Hoe werkt binaire zoekopdracht in een gesorteerde lijst?

Binaire zoekopdracht is een algoritme om een element te vinden in een gesorteerde lijst met een logaritmische complexiteit van O(log n). Het werkt volgens het principe "deel en heers":

1. Het middelste element van de lijst wordt bepaald.
2. Als het gezochte element gelijk is aan het middelste, stopt de zoekopdracht.
3. Als het gezochte element kleiner is dan het middelste, wordt de zoekopdracht voortgezet in de linkerhelft van de lijst.
4. Als het groter is, in de rechterhelft.

Het proces wordt recursief of iteratief herhaald totdat het element is gevonden of de zoekruimte op is.

Voorbeeld 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 niet gevonden
}