Kaip veikia dvejetainis paieška surūšiuotame sąraše?

Dvigubo paieškos algoritmas yra algoritmas, naudojamas rasti elementą surūšiuotame sąraše, su logaritmine sudėtingumu O(log n). Jis veikia pagal principą "skaldyk ir valdyk":

1. Nustatomas sąrašo vidinis elementas.
2. Jei ieškomas elementas yra lygus vidiniam, paieška baigiasi.
3. Jei ieškomas elementas yra mažesnis už vidinį, paieška tęsiasi kairėje sąrašo pusėje.
4. Jei didesnis, dešinėje.

Procesas kartojamas rekursyviai arba iteratyviai, kol elementas bus rastas arba paieškos diapazonas išseko.

Pavyzdys Go kalba:

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 // elementas nerastas
}