Чӣ гуна алгоритми ҷустуҷӯи дуӣ кор мекунад?

Икки қидирув, тартибланган массивни таҳлил қилиш ва қидирув интервалини давомида яримга бўлиш орқали ишлайди.

1. Бошланғич: Қидирув интервалининг сол ва ўнг чегаралари белгиланади (одатда массивнинг бошланиши ва охири).
2. Солиштириш: Интервалнинг ўртача индекси ҳисобланади. Ушбу индекстаги қиймат қидирилаётган элемент билан солиштирилади.
3. Интервални кичайтириш:
   • Агар ўртадаги қиймат қидирилаётган билан мос келса, элемент топилди.
   • Агар ўртадаги қиймат катта бўлса, қидирув интервалнинг ўнг яримида давом этади. Ўнг чегара ўртадан - 1 га кўчирилади.
   • Агар ўртадаги қиймат кичик бўлса, қидирув интервалнинг чап яримида давом этади. Чап чегара ўртадан + 1 га кўчирилади.
4. Такрорлаш: 2 ва 3-қадамлар элемент топилгунча ёки интервал бўш бўлгунча такрорланади.

Алгоритмнинг мураккаблиги O(log n), бу катта массивлар учун тўғри ва самарали бўлиб, линей қидирувдан анча самарали.

Pythonда мисол учун қуйидагича амалга оширилади:

def binary_search(arr, target):
    """
    Иккилик қидирувнинг амалга оширилиши.
    Тартибланган массив ва қидирилаётган қийматни олади.
    Элементнинг индекси ёки -1 қайтарилади, агар топилмаса.
    """
    чап, ўнг = 0, len(arr) - 1

    while чап <= ўнг:
        ўрта = (чап + ўнг) // 2  # Ўртача индекс ҳисобланади
        ўрта_қиймат = arr[ўрта]      # Ўртадаги қиймат олинади

        if ўрта_қиймат == target:
            return ўрта  # Элемент топилди
        elif ўрта_қиймат < target:
            чап = ўрта + 1  # Ўнгда қидириш
        else: # ўрта_қиймат > target
            ўнг = ўрта - 1 # Чапда қидириш

    return -1 # Элемент топилмади