Ikkilik qidiruv "Bo'lib tashla va hukmronlik qil" (Divide and Conquer) tamoyiliga asoslanadi. Algoritm ishlashi uchun massiv albatta saralangan (sorted) bo'lishi shart.

Vaqt murakkabligi: $O(\log n)$

Algoritmik samaradorlik nuqtayi nazaridan, Ikkilik qidiruv logarifmik vaqt murakkabligiga ega. Bu shuni anglatadiki, ma'lumotlar hajmi eksponental ravishda oshsa ham, bajariladigan amallar soni chiziqli tarzda juda sekin o'sadi.

O'rta nuqtani topish formulasi:

Odatda o'rta indeks quyidagicha hisoblanadi:

$$mid = \frac{low + high}{2}$$

Amaliy misol:

Bizda $\{-5, -2, 0, 1, 2, 4, 5, 6, 7, 10\}$ massiv bor. Bizning vazifamiz massiv ichidan $x=7$ sonini qidirish.

• Birinchi qadamda

Dastlab chap va o'ng chegaralarni belgilab olish butun massiv bo'yicha amalga oshiriladi. $Low=0$ va $High=9$ deb belgilanadi, markaziy element esa $Middle=(0+9)//2$ formulaga asosan hisoblanadi.

• Ikkinchi qadamda

$2 < 7$ bo'lgani uchun qidiruv sohasi o'ngga suriladi: $Low = 5$ va $High = 9$. Yangi markaziy element $Middle = (5 + 9) // 2 = 7$ formulasi orqali aniqlanadi. 7-indeksdagi qiymat (6) hali ham qidirilayotgan sondan kichik.

• Uchunchi qadamda

Soha yanada torayadi: $Low = 8$ va $High = 9$. Markaziy element $Middle = (8 + 9) // 2 = 8$ deb belgilanadi. 8-indeksdagi qiymat 7 ga teng ekanligi aniqlanadi va qidiruv muvaffaqiyatli yakunlanadi.

Yuqoridagi vizual jarayonni Python tilidagi funksiya ko'rinishida ifodalaymiz.

def binarySearch(arr, x):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  # O'rta indeksni topamiz

        if arr[mid] == x:        # Element topildi!
            return mid
        if arr[mid] > x:         # Target chap tomonda
            high = mid - 1
        else:                    # Target o'ng tomonda
            low = mid + 1
            
    return -1  # Element topilmadi