Hogyan működik a bináris keresés egy rendezett listában?

A bináris keresés egy olyan algoritmus, amely egy rendezett listában egy elem megtalálására szolgál, logaritmikus komplexitással O(log n). A "oszd meg és uralkodj" elven működik:

1. Meghatározza a lista középső elemét.
2. Ha a keresett elem megegyezik a középsővel, a keresés befejeződik.
3. Ha a keresett elem kisebb, a keresés a lista bal felében folytatódik.
4. Ha nagyobb, a jobb felében.

A folyamat rekurzívan vagy iteratívan ismétlődik, amíg az elem meg nem található vagy a keresési tartomány ki nem merül.

Példa Go nyelven:

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 // elem nem található
}