Каква е сложността на двоичното търсене и защо?

Сложността на двоичното търсене е O(log n), където n е броят на елементите в сортирания масив. Това се дължи на факта, че на всяка стъпка алгоритъмът дели областта за търсене на две, изключвайки половината от елементите, които не могат да съдържат търсената стойност. По този начин броят на операциите расте логаритмично спрямо размера на входните данни.

Пример на 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 // елементът не е намерен
}