Binary search

03-08-2024

---

Binary search

Binary search tartiblangan ro'yxatlar uchun samarali qidirish algoritimi.

Misol uchun, test ballarining saralangan ro'yxatidan agar sinfdagi kimdir 80 ball olganligini aniqlamoqchi bo'lsak, u tezda javob topish uchun ro'yxatda ikkilik qidiruvni amalga oshirishi mumkin. Ikkilik qidiruv ko'rib chiqish uchun elementlar sonini ikki baravar kamaytirish orqali kerakli qiymatni aniqlaydi. Ikkilik qidiruv elementning roʻyxatda bor yoki yoʻqligini aniqlaydi.

Amaliyot

items = [1, 2, 3, 6, 7, 9, 12, 36, 46, 59, 67, 69, 71, 73, 85, 96, 101]

def binary_search(items, item):
    first_index = 0
    last_index = len(items) - 1
    while first_index <= last_index:
        mid = (first_index + last_index) // 2
        if items[mid] == item:
            return mid
        else:
            if item < items[mid]:
                last_index = mid - 1
            else:
                first_index = mid + 1
    return None

print(binary_search(items, 69))

Kamchiligi

Binary search algoritimini kamchiligi faqat tartiblangan ro'yxatlar uchun ishlaydi.