Урок 40

Двоичный (бинарный) поиск элемента

Двоичный поиск значения в списке (или массиве) используется для упорядоченных последовательностей (отсортированных по возрастанию или убыванию). Заключается такой поиск в определении, содержит ли массив определенное значение, а также определение места его нахождения.

Описание алгоритма

1. Находится средний элемент последовательности. Для этого первый и последний элементы связываются с переменными, а средний вычисляется.
2. Средний элемент сравнивается с искомым значение. В зависимости от того, больше оно или меньше среднего элемента, дальнейший поиск будет происходить лишь в левой или правой половинах массива. Если значение среднего элемента окажется равным искомому, то поиск завершен.
3. Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.
4. Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется уже для данной последовательности.

Исходный код на Python

li = [0,3,5,7,10,20,28,30,45,56]
x = 45
i = 0
j = len(li)-1
m = int(j/2)
while li[m] != x and i <=j:
    if x > li[m]:
        i = m+1
    else:
        j = m-1
    m = int((i+j)/2)
 
 
if i > j:
    print('Элемент не найден')
else:
    print('Индекс элемента: ', m)