Икілік издөө алгоритми кандай иштейт?

Икки тараптуу издөө, иреттелген массивти анализдөө жана издөө интервалын үзгүлтүксүз бөлүп, иштейт.

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 # Элемент табылган жок