İkili axtarış ideya baxımından sadədir, amma praktikada ən çox səhv buraxılan alqoritmlərdəndir. Bu mövzuda sərhədlərlə bağlı tələləri, dublikatlarda birinci və sonuncu uyğunluğu və standart bisect modulunu görəcəksiniz.
![[1, 2, 2, 2, 5, 8] içində 2 üçün aşağı və yuxarı sərhəd](img/lessons/algorithms/binary-search-pitfalls-bounds.svg)
Sərhədlər: qapalı və yarıaçıq interval
Əvvəlki mövzuda [lo, hi] qapalı intervalı işlətdik (hi = len(a) - 1, lo <= hi, hi = mid - 1). Dublikatlar və "yerləşdirmə mövqeyi" üçün yarıaçıq [lo, hi) şablonu rahatdır: hi = len(a), lo < hi, hi = mid. Hər şablonun öz invariantı var və onları qarışdırmaq IndexError, sonsuz dövr və ya bir vahid səhvi verir. Qayda: bir şablon seçin və onun bütün üç hissəsini (başlanğıc, şərt, yeniləmə) birlikdə saxlayın.
Birinci və sonuncu uyğunluq: lower_bound və upper_bound
lower_bound(a, x) ilk i mövqeyidir ki, a[i] >= x; upper_bound(a, x) isə ilk a[i] > x. İkisi də 0..len(a) aralığında mövqe qaytarır (xana yox), x olmasa belə sıranı saxlayan yeri göstərir. Birinci uyğunluq lower_bound, sonuncu upper_bound - 1, say isə upper_bound - lower_bound-dur. Eyni kod x-in olub-olmadığını da yoxlayır: i < len(a) and a[i] == x.
