İkili axtarışın mürəkkəbliyi nədir və niyə?

İkili axtarışın mürəkkəbliyi O(log n)-dir, burada n sıralanmış massivdəki elementlərin sayıdır. Bu, hər addımda axtarış sahəsinin yarıya bölünməsi və axtarılan dəyəri içerməyən elementlərin yarısının rədd edilməsi ilə əlaqədardır. Beləliklə, əməliyyatların sayı giriş məlumatlarının ölçüsü ilə logarifmik şəkildə artır.

Go dilində nümunə:

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 // element tapılmadı
}