İkili axtarış (binary search) çeşidlənmiş ardıcıllıqda hədəfi tapmağın ən məşhur üsuludur. Hər addımda ortadakı elementlə müqayisə edirik və hədəfin ola bilməyəcəyi yarını atırıq. Vaxt O(log n): milyard elementdə cəmi 30 addım. Müqayisə üçün: xətti axtarış O(n).

![[2, 5, ..., 91] içində 23-ün axtarışı: üç addım](img/lessons/algorithms/binary-search-trace.svg)

Alqoritm və invariant

İki sərhəd saxlayırıq: lo və hi, onlar qapalı interval a[lo..hi] verir. İnvariant: x siyahıdadırsa, o bu intervaldadır. mid = (lo + hi) // 2 ortadır. a[mid] == x olarsa, tapdıq. a[mid] < x olarsa, x yalnız sağda ola bilər: lo = mid + 1. Əks halda sol: hi = mid - 1. Interval boşalanda (lo > hi) x yoxdur. Hər addım intervalı yarıya endirir, buna görə addımların sayı floor(log2 n) + 1-dən çox deyil.

python
def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:                 # x, if present, lies in a[lo..hi]
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            lo = mid + 1            # discard the left half
        else:
            hi = mid - 1            # discard the right half
    return -1