Tartiblangan ro'yxatda binar qidiruv qanday ishlaydi?

Ikki qidiruv, tartiblangan ro'yxatda elementni topish uchun logarifmik murakkablikka ega O(log n) algoritmidir. "Bo'lakla va hukmronlik qil" tamoyili bilan ishlaydi:

1. Ro'yxatning o'rtacha elementi aniqlanadi.
2. Agar qidirilayotgan element o'rtacha elementga teng bo'lsa, qidiruv tugaydi.
3. Agar qidirilayotgan element o'rtacha elementdan kichik bo'lsa, qidiruv ro'yxatning chap yarimida davom etadi.
4. Agar katta bo'lsa, o'ng yarimda davom etadi.

Jarayon rekursiv yoki iterativ tarzda takrorlanadi, element topilmaguncha yoki qidiruv diapazhi tugaguncha.

Go tilida misol:

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 topilmadi
}