Qidiruv algoritmi qanday ishlaydi?

Ikki qidirish, tartiblangan massivni tahlil qilish va qidiruv diapazonini ketma-ket ravishda yarimga bo‘lish orqali ishlaydi.

1. Boshlash: Qidiruv diapazonining chap va o‘ng chegaralari aniqlanadi (odatda massivning boshlanishi va oxiri).
2. Solishtirish: Diapazonning o‘rtacha indeksini hisoblash. Bu indeksdagi qiymat qidirilayotgan element bilan solishtiriladi.
3. Diapazonni qisqartirish:
   • Agar o‘rtadagi qiymat qidirilayotgan bilan mos kelsa, element topildi.
   • Agar o‘rtadagi qiymat qidirilayotganidan katta bo‘lsa, qidiruv diapazonining chap yarmida davom etadi. O‘ng chegarasi o‘rtadan - 1 ga siljiydi.
   • Agar o‘rtadagi qiymat qidirilayotganidan kichik bo‘lsa, qidiruv diapazonining o‘ng yarmida davom etadi. Chap chegarasi o‘rtadan + 1 ga siljiydi.
4. Takrorlash: 2 va 3-qadamlar element topilguncha yoki qidiruv diapazoni bo‘sh bo‘lgunga qadar takrorlanadi.

Algoritmning murakkabligi O(log n), bu katta massivlar uchun chiziqli qidiruvdan ancha samaraliroq.

Pythonda misol uchun quyidagicha amalga oshiriladi:

def binary_search(arr, target):
    """
    Ikki qidiruvni amalga oshirish.
    Tartiblangan massiv va qidirilayotgan qiymatni oladi.
    Elementning indeksini yoki topilmasa -1 ni qaytaradi.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # O‘rtacha indeksni hisoblash
        mid_val = arr[mid]      # O‘rtadagi qiymatni olish

        if mid_val == target:
            return mid  # Element topildi
        elif mid_val < target:
            left = mid + 1  # Qidirilayotgan katta, o‘ngda qidirish
        else: # mid_val > target
            right = mid - 1 # Qidirilayotgan kichik, chapda qidirish

    return -1 # Element topilmadi