Как работи алгоритъмът за двоично търсене?

Бинарното търсене работи, като анализира сортиран масив и последователно дели интервала за търсене на половини.

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 # Елементът не е намерен