Чӣ тавр ҷустуҷӯи бинарӣ дар рӯйхати тақсимшуда кор мекунад?

Ҷустуҷӯи дугона як алгоритми ҷустуҷӯи унсури дар рӯйхати тартибдодашуда бо мураккабии логарифмикӣ O(log n) мебошад. Он асос ёфтааст ба принсипи "ҳисоб ва ҳукмронӣ":

1. Унсури марказии рӯйхат муайян карда мешавад.
2. Агар унсури ҷустуҷӯӣ баробар ба марказ бошад, ҷустуҷӯ ба анҷом мерасад.
3. Агар унсури ҷустуҷӯӣ хурдтар аз марказ бошад, дар нимҷазираи чапи рӯйхат идома медиҳад.
4. Агар калонтар бошад, дар нимҷазираи рост.

Процесро такрор мекунад рекурсивӣ ё итеративӣ, то ки унсур ёфтан ё диапазони ҷустуҷӯ тамом шавад.

Масалан дар 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 // унсур ёфт нашуд
}