Обяснете принципа на работа на алгоритъма за двоично търсене и основните му стъпки.

Бинарното търсене е ефективен алгоритъм за намиране на елемент в сортиран масив. Принципът му се състои в последователно делене на областта за търсене на половина и сравняване на търсената стойност с елемента в средата.

Основни стъпки:

1. Определете началните граници на търсенето: леви и десни индекси.
2. Намерете средния индекс: mid = (left + right) // 2.
3. Сравнете търсената стойност с елемента в mid.
   • Ако са равни, върнете индекса mid.
   • Ако търсената стойност е по-малка, преместете десния граница на mid - 1.
   • Ако е по-голяма, преместете левия граница на mid + 1.
4. Повтаряйте стъпки 2-3, докато левият граница не надмине десния.

Ако елементът не бъде намерен, върнете например -1.

Пример на Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1