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

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

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

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)

Замена элементов в списке

Заменить в списке элементы с одним значением на другое.

# Замена элементов в списке.

# Демонстрация использования методов списка.

lst = [10, 45, 24, 43, 89, 15, 16, 23, 89, 23, 35, 64, 21, 12, 45]

print(lst)

item = input('Еnter item: ')

item = int(item)

item1 = input('Еnter new item: ')

item1 = int(item1)

#~ j = 0

#~ for i in lst:

#~ if i == item:

#~ lst.remove(i)

#~ lst.insert(j,item1)

#~ j += 1

for i in lst:

if i == item:

j = lst.index(i)

print(j)

lst.remove(i)

lst.insert(j,item1)

print(lst)

Перевод чисел из десятичной системы счисления в двоичную

Один из алгоритмов получения двоичного числа из десятичного можно описать следующим образом:

1. Исходное десятичное число делится на два (основание двоичной системы счисления).

2. В одну переменную записывается частное в виде целого числа, в другую – остаток в виде строки (если остатка нет, то записывается ноль).

3. Если частное не было равно нулю, то оно снова делится на два. Переменная, связанная со старым частным связывается с новым (прежнее частное теряется). Новый остаток с помощью операции конкатенации добавляется в начало строковой переменной, где хранятся остатки.

4. П. 3 продолжает повторяться до тех пор, пока частное не станет равно нулю.

5. Остатки от деления, записанные в обратном порядке, представляют собой двоичное представление заданного десятичного числа.

x = int(input("Введите натуральное число: "))

n = ""

while x > 0:

y = str(x % 2)

n = y + n

x = int(x / 2)

print (n)