@kamchatkachild

Обратите внимание, что перед отправкой решения данной задачи нужно в качестве языка выбрать Make.

В процессе археологических раскопок было найдено много документов. Откапывая все новые и новые рукописи, археологи датировали их и складывали в одну стопку. У одного из археологов родилась новая гипотеза о причинах поражения Французов в битве 1415 года при Азенкуре. Однако, для проверки гипотезы необходимо найти документ 1415 года. Вам дан список дат, которые приписаны к каждому документу. Даты упорядочены строго по возрастанию. При помощи бинарного поиска найдите индекс соответствующего документа. Гарантируется, что документ 1415 года есть в списке.

Вам нужно реализовать функцию с именем bin_search(lst) со следующими требованиями:

1) Имя функции - строго фиксировано (bin_search).

2) Функции подаётся на вход список lst (список строк, каждая из которых является строковым представлением соответствующей даты. Например: ['1000', '1280', '1415'])

3) Функция возвращает число (искомый индекс 1415 года во входном списке).

4) В качестве отступов в функции используется 4 пробела.

5) Функция реализует алгоритм бинарного поиска.

Приведём пример функции, которую следует сдавать в тестовую систему (в данном случае реализован не бинарный поиск, а обычный, поэтому такое решение засчитано не будет):

def bin_search(lst):
for i in range(len(lst)):
if int(lst[i])==1415:
return i
Формат ввода
Входной параметр функции представляет список строк- дат.

Формат вывода
Вывести в качестве возвращаемого функцией bin_search(lst) значения (через return) индекс i элемента со значением '1415'.

Пример :
Ввод 1414 1414 1415 Вывод 2

Примечания
1) Отсчёт индексов начинается с нуля.

2) Обратите внимание, что входной параметр функции - список строк.

3) Нужно реализовать бинарный поиск, который работает достаточно быстро. Остальные, менее эффективные алгоритмы (например, с find()) не пройдут по ограничению времени. В этом случае будет получена ошибка Runtime Error (RE).

4) Не забывайте, что во входных данных числа представлены в виде строк. Обычное сравнение строк происходит в лексикографическом порядке. Т.е. '111'<'12'. Нам же нужно сравнивать именно числа. Поэтому внутри бинарного поиска перед сравнением нужно выполнять преобразование строк к int.

5) Преобразование всех элементов исходного списка к int занимает много времени. В бинарном поиске нам не нужны все значения списка. Мы только смотрим на середины отдельных срезов исходного списка. Поэтому нужно выполнять преобразование строки к int только для тех элементов, которые мы сравниваем с числом 1415.

6) Вообще говоря, бинарный поиск работает только с отсортированным списком.

7) В нашем случае не нужно дополнительно сортировать исходный список, т.к. он уже отсортирован (см. условие).

8) При проверке собственной реализации бинарного поиска рассмотрите ситуации:
- список из одного элемента,
- список из чётного количества элементов,
- список из нечётного количества элементов (больше одного).

Вот, что получилось у меня, но это неправильно. Я не очень понимаю эту тему, можете помочь, пожалуйста?

def bin_search(lst):

low = 0
high = len(lst) - 1

while low <= high:

middle = (low + high)//2

if int(lst[i]) == 1415:
return i

0