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

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

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

  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)

Если старательно не избегать

Если старательно не избегать заложенных в Python средств, то для поиска значения value в списке lst получим:

[i for i,v in enumerate(lst) if v == value]

В отличие от первого варианта, этот код дает индексы всех вхождений искомого значения.

Кроме того, в стандартной библиотеке Python есть модуль bisect.

Алгоритм не правильно работает

Протестируйте когда x == -1, 0, 15, 25, 56, 100

Код выше исправлен. Это

Код выше исправлен.

Это прежний (содержащий ошибку) для сравнения:

li = [0,3,5,7,10,20,28,30,45,56] # исходный список
x = 28 # искомое значение
 
i = 1 # первый элемент
j = len(li) # последний элемент
m = int((i + j) / 2) # середина (приблизительно)
 
# пока искомое значение не равно текущей середине
# или левая граница зашла за правую (элемент не найден)
while li[m]!=x or i>j: 
     m = int((i + j) / 2) # найти новую середину
     if x > li[m]: # если значение больше серединного
          i = m + 1 # то сместить левую границу за середину
     else: # иначе
          j = m - 1 # переместить правую границу до середины
 
if i > j:
     print ("Элемент не найден")
else:
     print (m) # вывести индекс искомого элемента