Kā darbojas binārā meklēšana sakārtotā sarakstā?

Dvieļu meklēšana ir algoritms, kas tiek izmantots, lai atrastu elementu sakārtotā sarakstā ar loģaritmisko sarežģītību O(log n). Tas darbojas pēc principa "dalīt un valdīt":

1. Nosaka saraksta vidējo elementu.
2. Ja meklētais elements ir vienāds ar vidējo, meklēšana beidzas.
3. Ja meklētais elements ir mazāks par vidējo, meklēšana turpinās kreisajā saraksta daļā.
4. Ja lielāks, tad labajā daļā.

Process tiek atkārtots rekursīvi vai iteratīvi, līdz elements tiek atrasts vai meklēšanas diapazons izsmelts.

Piemērs Go valodā:

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 // elements nav atrasts
}