---

def binary_search(arr, target):
    left = 0                      # левая граница поиска
    right = 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                     # элемент не найден