Sıralanmış siyahıda ikili axtarış necə işləyir?

İkili axtarış, sıralanmış bir siyahıda element tapmaq üçün logarifmik mürəkkəblik O(log n) olan bir algoritmdir. "Böl və hökmranlıq et" prinsipinə əsaslanır:

1. Siyahının orta elementi müəyyən edilir.
2. Əgər axtarılan element orta elementə bərabərdirsə, axtarış bitir.
3. Əgər axtarılan element orta elementdən kiçikdirsə, axtarış siyahının sol yarısında davam edir.
4. Əks halda, sağ yarısında davam edir.

Proses rekursiv və ya iterativ olaraq təkrarlanır, element tapılana və ya axtarış diapazonu tükənənə qədə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ılmayıb
}