Binary search və axtarış pattern-ləri

Binary search hər addımda axtarış sahəsini yarıya bölür: n elementdə cəmi log₂ n addım. 1 milyard elementdə bu, 30 addımdır.

Şərt: massiv sıralanmış olmalıdır. Amma bu şərtin daha ümumi və daha faydalı formulası var: axtarış sahəsində elə bir monoton keçid olmalıdır ki, hansısa nöqtədən sonra cavab "yox"dan "bəli"yə dəyişsin və bir daha geri qayıtmasın. Sıralanmış massiv bunun sadəcə ən tanış halıdır — bu ümumiləşdirmə mövzunun sonundakı ən güclü pattern-in açarıdır.

Bir dəfə axtarırsansa, sıralamaq sərfəli deyil: sortun özü O(n log n)-dir, xətti axtarış isə O(n). Binary search yalnız data onsuz da sıralıdırsa və ya bir dəfə sıralayıb çox dəfə axtaracaqsansa qazandırır. Bu mühakiməni interview-da ucadan söyləmək lazımdır — çox namizəd "sıralayıb binary search edərəm" deyib bir dəfəlik axtarışı bahalaşdırır.

Binary search-in yazılması asan görünür, amma statistikaya görə peşəkar proqramçıların əksəriyyəti onu ilk cəhddə səhvsiz yaza bilmir. Səbəb üç tələdir.

Tələ 1 — `mid` hesablamasında overflow. (lo + hi) / 2 sabit bitli tam ədədlərdə (Kotlin/Java Int, C++ int) lo və hi böyük olanda mənfi ədəd verir. Düzgün forma: `lo + (hi - lo) / 2`. JavaScript-də ədədlər 64-bit float olduğuna görə bu overflow praktikada baş vermir, amma (lo + hi) >> 1 yazsan başqa tələyə düşürsən: bitwise operatorlar operandı 32-bit-ə sıxır və 2³¹-dən böyük indekslərdə nəticə pozulur.

Tələ 2 — sonsuz döngə. hi = mid yazıb lo-nu mid-də saxlasan (yəni lo = mid), iki elementli aralıqda mid həmişə lo-ya bərabər olur və döngə heç vaxt bitmir. Qayda: hər iterasiyada aralıq mütləq kiçilməlidir — bir tərəf mid + 1 və ya mid - 1 olmalıdır.

Tələ 3 — off-by-one. hi = n yoxsa hi = n - 1? while (lo < hi) yoxsa while (lo <= hi)? Bu qərarlar bir-birindən asılıdır və qarışdırılanda ya sonuncu element yoxlanmır, ya da massivdən kənara çıxılır.

Həll — loop invariant üsulu. Bir dəfə seçib həmişə ona sadiq qal:

• Aralığı yarıaçıq götür: [lo, hi) — yəni lo = 0, hi = n (uzunluq, sonuncu indeks yox)
• Döngə şərti while (lo < hi)
• İnvariant: cavab həmişə `[lo, hi)` aralığındadır
• mid uyğun gəlmirsə lo = mid + 1, uyğun gəlirsə hi = mid (mid-in özü hələ namizəddir)
• Döngə bitəndə lo == hi və cavab məhz odur

Bu şablon sonsuz döngə verə bilmir, çünki lo artır və ya hi azalır. Üstəlik o, birbaşa lower bound (şərti ödəyən ilk indeks) qaytarır — və aşağıdakı variantların hamısı bunun üzərində qurulur.

Cavab sahəsində binary search — namizədlərin ən çox buraxdığı pattern və məhz ona görə interview-da fərqləndirici sual kimi istifadə olunur.

Əsas fikir: binary search-in massivə heç bir aidiyyəti yoxdur. Ona lazım olan yalnız monoton feasible(x) funksiyasıdır — elə bir funksiya ki, müəyyən həddən sonra həmişə true qaytarsın:

false, false, false, TRUE, true, true, ...

Bu şərt ödənirsə, ilk true-nu log addımda tapa bilərsən — hətta axtardığın şey massivdə heç olmasa da.

Tanıma əlaməti: məsələdə "minimum elə X tap ki...", "maksimum elə X tap ki...", "ən azı neçə...", "ən çoxu nə qədər..." ifadələri varsa və X-i sınamaq asandırsa, bu pattern-dir.

Şablon:

• Cavabın mümkün diapazonunu müəyyən et: lo = ən kiçik mənalı cavab, hi = zəmanətli işləyən cavab
• feasible(x) yaz — adətən sadə xətti keçid, O(n)
• Adi lower bound şablonunu işlət: feasible(mid) → hi = mid, əks halda lo = mid + 1
• Mürəkkəblik: O(n log(diapazon))

Klassik nümunələr: paketləri D günə daşımaq üçün minimum gəmi tutumu; Koko-nun bananları H saata yeməsi üçün minimum sürət; n kitabı k tələbəyə elə bölmək ki, maksimum yük minimal olsun; tam ədəd kvadrat kök; verilmiş büdcə ilə maksimum server sayı.

Kritik yoxlama: feasible həqiqətən monotondurmu? Əgər "bəli" cavabından sonra yenidən "yox" gələ bilirsə, binary search tətbiq olunmur. Bunu interview-da ucadan yoxlamaq — "tutum artdıqca lazım olan gün sayı yalnız azala bilər, yəni monotondur" — cavabın ən güclü hissəsidir.