Двоичный поиск значения в списке (или массиве) используется для упорядоченных последовательностей (отсортированных по возрастанию или убыванию). Заключается такой поиск в определении, содержит ли массив определенное значение, а также определение места его нахождения.
Описание алгоритма
- Находится средний элемент последовательности. Для этого первый и последний элементы связываются с переменными, а средний вычисляется.
- Средний элемент сравнивается с искомым значение. В зависимости от того, больше оно или меньше среднего элемента, дальнейший поиск будет происходить лишь в левой или правой половинах массива. Если значение среднего элемента окажется равным искомому, то поиск завершен.
- Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.
- Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется уже для данной последовательности.
Исходный код на Python
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) # вывести индекс искомого элемента
