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

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

При решении задачи на языке программирования Python вместо массива используется список

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

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

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

from random import randint

# создание списка, его сортировка по возрастанию и вывод на экран
a = []
for i in range(10):
    a.append(randint(1, 50))
a.sort()
print(a)

# искомое число
value = int(input())

# индексы первого элемента, последнего и среднего
low = 0
high = len(a) - 1
mid = len(a) // 2

while a[mid] != value and low <= high:
    if value > a[mid]:
        low = mid + 1
    else:
        high = mid - 1
    mid = (low + high) // 2

if low > high:
    print('No value')
else:
    print('ID =', mid)

Примеры выполнения:

[6, 17, 21, 27, 32, 35, 35, 36, 37, 48]
27
ID = 3

[4, 5, 12, 13, 13, 18, 22, 26, 30, 35]
28
No value

Другие варианты решения задачи двоичного поиска на Python:

from random import randint

a = [randint(1, 50) for i in range(10)]
a.sort()
print(a)

value = int(input())

left = 0
right = len(a) - 1
center = (left + right) // 2

while a[center] != value:
    if value > a[center]:
        left = center + 1
    else:
        right = center - 1
    center = (left + right) // 2
    if left >= right:
        break

if value == a[center]:
    print('ID =', center)
else:
    print('No value')

from random import randint

a = [randint(1, 50) for i in range(10)]
a.sort()
print(a)

value = int(input())

left = 0
right = len(a) - 1

while left <= right:
    center = (left + right) // 2
    if value == a[center]:
        print('ID =', center)
        break
    if value > a[center]:
        left = center + 1
    else:
        right = center - 1
else:
    print('No value')

Больше задач в PDF