Бинарный поиск: индекс элемента

Дан отсортированный по неубыванию список целых чисел arr и число target.

Реализуйте функцию binary_search(arr, target), которая возвращает индекс элемента, равного target, или -1, если такого элемента нет. Если подходящих элементов несколько, можно вернуть индекс любого из них. Алгоритм должен работать за O(log n).

Формат входа: arr — отсортированный список (возможно пустой), target — целое число.

Формат выхода: целое число — индекс или -1.

Примеры:

binary_search([1, 3, 5, 7, 9], 7) -> 3
binary_search([1, 3, 5, 7, 9], 4) -> -1
binary_search([], 5) -> -1