Kāda ir binārās meklēšanas sarežģītība un kāpēc?

Dvieļu meklēšanas sarežģītība ir O(log n), kur n ir sakārtota masīva elementu skaits. Tas ir tāpēc, ka katrā solī algoritms sadala meklēšanas apgabalu uz pusi, noraidot pusi elementu, kas nevar saturēt meklēto vērtību. Tādējādi operāciju skaits pieaug logaritmiski atkarībā no ievades datu lieluma.

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 netika atrasts
}