Бінарний пошук

Реалізуйте функцію, яка виконує бінарний пошук у відсортованому масиві цілих чисел. Функція повинна отримати на вхід відсортований список та цільове число, і повернути індекс знайденого елемента або -1, якщо елемент не знайдено.

Сигнатура функції має бути такою:

def binary_search(arr: list[int], target: int) -> int:

Бінарний пошук працює за таким принципом:

1. Обирається середній елемент масиву.
2. Якщо середній елемент дорівнює шуканому числу, повертаємо його індекс.
3. Якщо шукане число менше за середній елемент, повторюємо пошук у лівій половині масиву.
4. Якщо шукане число більше, повторюємо пошук у правій половині масиву.
5. Процес повторюється, поки не буде знайдено число або поки масив не стане порожнім.

Алгоритм повинен працювати за логарифмічний час O(log n).

Приклад

>>> binary_search([1, 3, 5, 7, 9, 11, 13], 7)
3
>>> binary_search([1, 3, 5, 7, 9, 11, 13], 4)
-1
>>> binary_search([2, 4, 6, 8, 10], 10)
4
>>> binary_search([], 5)
-1

Підказки щодо реалізації

• Використовуйте два індекси (left, right), щоб визначати межі поточного підмасиву.
• Використовуйте цикл або рекурсію для пошуку середнього елемента.
• Якщо left > right, то елемент не знайдено.
• Пам’ятайте про цілочисельне ділення при знаходженні середнього індексу.