Binar qidiruv: qanday ishlaydi va qanday amalga oshiriladi

Bir daqiqada g‘oya

Binar qidiruv faqat saralangan ma’lumotlarda ishlaydi. Barcha elementlarni ko‘rib chiqish o‘rniga diapazon o‘rtasiga qaraymiz:

• o‘rtadagi element qidirilayotganga teng bo‘lsa — topildi;
• kichik bo‘lsa — qidirilayotgan o‘ngda, chap yarmini tashlaymiz;
• katta bo‘lsa — chapda, o‘ng yarmini tashlaymiz.

Har qadam diapazonni ikkiga bo‘ladi, shuning uchun murakkablik — O(log n). Million element uchun bu million emas, taxminan yigirmata solishtirish.

Iterativ amalga oshirish

Yopiq interval [lo, hi] ishlatamiz: ikkala chegara ham qidiruvga kiradi.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Muhim tafsilotlar:

• Shart lo <= hi, chunki lo == hi bo‘lganda yana bitta nomzod qoladi.
• Siljish mid + 1 va mid - 1, chunki mid allaqachon tekshirilgan.
• (lo + hi) // 2 o‘rniga lo + (hi - lo) // 2 qat’iy o‘lchamli butun sonli tillarda (Java, C++) to‘lib ketishdan himoya qiladi. Python’da shart emas, lekin odat foydali.

Rekursiv amalga oshirish

def binary_search_rec(a, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if a[mid] == target:
        return mid
    if a[mid] < target:
        return binary_search_rec(a, target, mid + 1, hi)
    return binary_search_rec(a, target, lo, mid - 1)

Mantiq o‘sha, lekin har qadam — yangi chaqiruv. Rekursiya chuqurligi atigi O(log n), shuning uchun stek to‘lib ketmaydi. Shunday bo‘lsa-da, iterativ versiyani odatda tuzatish osonroq va u stek xotirasini sarflamaydi.

Bittaga adashish xatolari

Binar qidiruvdagi xatolarning ko‘pi — off-by-one. Ulardan qochish uchun bitta kelishuvni tanlang va unga amal qiling:

Odatiy muammolar:

• Cheksiz sikl: lo < hi bilan lo = mid aralashtirilgan. Diapazon torayishdan to‘xtaydi.
• Element o‘tkazib yuborilgan: yopiq intervalda lo < hi yozilgan.
• Massivdan chiqib ketish: hi = n bo‘lib, a[hi] ga murojaat qilinadi.

Kodni bo‘sh massivda, bitta elementli massivda, qidirilayotgan boshida, oxirida va mavjud bo‘lmagan qiymatda tekshiring.

Birinchi uchrashuvni topish

Massivda takrorlar bo‘lsa, oddiy versiya istalgan mosini qaytaradi. Birinchisini (lower bound) topish uchun moslik topilganda to‘xtamay, chapga harakatni davom ettiramiz:

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # first index where a[i] >= target

Agar lo < len(a) va a[lo] == target bo‘lsa, bu birinchi uchrashuv. Xuddi shunday upper bound (a[mid] <= target sharti) oxirgi uchrashuvdan keyingi indeksni beradi. Uchrashuvlar soni — ularning farqi. Python’da buning uchun bisect moduli, C++ da std::lower_bound va std::upper_bound bor.

Javob bo‘yicha binar qidiruv

Bu usul faqat massivlar uchun emas. Agar javob diapazondagi son bo‘lsa va «x mos keladimi» tekshiruvi monoton bo‘lsa (qaysidir nuqtagacha hammasi «yo‘q», keyin «ha»), javobning o‘zini binar qidirish mumkin.

Misol: posilkalarni D kunda yetkazish uchun minimal yuk ko‘tarish quvvati.

1. Pastki chegara — eng og‘ir posilka, yuqori chegara — hammasining yig‘indisi.
2. can(capacity) funksiyasi D kun yetarli ekanini ochko‘z (greedy) usulda tekshiradi.
3. can «ha» qaytaradigan eng kichik qiymat o‘sha lower bound shabloni bilan topiladi.

Shu yo‘l bilan butun sonli kvadrat ildiz, minimal vaqt va eng kichik masofani maksimallashtirish masalalari yechiladi.