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

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

×

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

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

Здесь мы исходим из того, что список отсортирован по возрастанию. Вариант двоичного поиска в отсортированном по убыванию массиве рассмотрен в конце этой статьи.

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

Исходный код на 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

В коде выше мы используем выход левой границы за правую как сигнал об отсутствии значения в списке. В этом случае цикл выполняет одну лишнюю итерацию, так как то, что значения нет, понятно уже при ложности выражения a[mid] != value and low < high, когда low становится равным high. Однако в этом случае при выходе из цикла мы никаким образом не можем знать, было найдено или нет значение, так как ситуация, при которой все три границы (нижняя, верхняя и середина) будут равны друг другу, может соответствовать и тому и другому. В этом случае проверкой в заголовке if после цикла должно быть выражение a[mid] != 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')

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

По сравнению с отсортированным по возрастанию списком, в случае расположения элементов по убыванию в алгоритме надо поменять на обратные условия при сдвиге границ. Если искомое значение меньше значения в текущей середине, то искать его надо справа от нее. Значит, сдвигается левая граница за границу середины. Если же искомое значение больше срединного, сдвигаем правую границу ближе к началу массива.

from random import randint

a = [randint(1, 50) for i in range(10)]
a.sort(reverse=True)  # сортировка по убыванию
print(a)

value = int(input())
index = None

left = 0
right = len(a) - 1

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

if index:
    print('ID =', index)
else:
    print('No value')

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