Kako funkcioniše algoritam binarnog pretraživanja?

Бинарно претраживање ради анализирајући сортирани низ, делећи интервал претраге изнова на пола.

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 # Елемент није пронађен