Главная » Реализация известных алгоритмов на языке программирования Python

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

Опубликовано plustilino в Январь 10, 2010 - 13:49. Changed Март 27, 2011 - 17:36

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

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

  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)
#1Опубликовано Гость в Февраль 26, 2011 - 17:55.

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

Протестируйте когда x == -1, 0, 15, 25, 56, 100
#2Опубликовано plustilino в Март 27, 2011 - 17:34.

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

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

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

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) # вывести индекс искомого элемента