Алгоритм Бинарного Поиска на Python

О том что это такое можно почитать вот ЗДЕСЬ. Мой пост о самом алгоритме. Мне было интересно написать и проверить этот алгоритм. Это алгоритм поиска, прикол в том, что если мы увеличиваем наш список вдвое, то количество поисковых запросов увеличивается  на 1.

Длина списка 20 - макс. кол. запросов 4

Длина списка 40 - макс. кол. запросов 5

Длина списка 80 - макс. кол. запросов 6

И так далее...

Получается, что абсолютно не важно как много номеров в вашей телефонной книге, ваш телефончик моментально всё найдёт.

Я его написал вот так (гугл тоже помогал :) ):

Я импортировал Randint для рандомального разброса чисел и задал переменные. Так же мне было интересно поработать с форматированием текста:

from random import randint lis = [] y = 0 txt = "Есть контакт!! Что что вы искали находится на {} месте." txt2 = "Количество попыток поиска: {}"

Затем создаём сам список. Так же можно задать длину списка. Это я сделал для того, что бы можно было посмотреть как быстро производится поиск в зависимости от длины списка.

dlinnaSpiska = int(input("Какова длина списка? ")) for x in range(dlinnaSpiska): lis.append(randint(1, dlinnaSpiska + 1)) lis.sort()

Затем мы задаём число которое надо найти. Первый же if проверяет если наше число не выходит за рамки списка. Если оно не в рамках то какой смысл продолжать? А если оно таки в рамках списка то тогда идёт разбор списка по минимум, максимум и середине.

if iskat < lis[0] or iskat > lis[dlinnaSpiska - 1]: print("Нет такого слова в этой букве!") else: dlinna = len(lis) mini = 0 maxi = dlinna - 1 midi = dlinna // 2

Далее идёт сам алгоритм поиска. При каждом запросе отсеивается половина списка. Какую половину отсеивать, большую или меньшую, решается в зависимости от положения нашего числа от середины списка. И если в конечном итоге наше число будет в середине - значит алгоритм его нашел. В противном случаем программа скажет что его нет в списке.

while lis[mini] <= lis[maxi] and iskat != lis[midi]: if iskat > lis[midi]: mini = midi + 1 else: maxi = midi - 1 midi = (mini + maxi) // 2 y += 1

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

if mini > maxi: print("Нет такого слова в этой букве!") print(txt2.format(y)) else: place = midi print(txt.format(place)) print(txt2.format(y))

И весь код целиком:

from random import randint lis = [] y = 0 txt = "Есть контакт!! Что что вы искали находится на {} месте." txt2 = "Количество попыток поиска: {}" dlinnaSpiska = int(input("Какова длина списка? ")) for x in range(dlinnaSpiska): lis.append(randint(1, dlinnaSpiska + 1)) lis.sort() iskat = int(input("Какое число искать? ")) if iskat < lis[0] or iskat > lis[dlinnaSpiska - 1]: print("Нет такого слова в этой букве!") else: dlinna = len(lis) mini = 0 maxi = dlinna - 1 midi = dlinna // 2 while lis[mini] <= lis[maxi] and iskat != lis[midi]: if iskat > lis[midi]: mini = midi + 1 else: maxi = midi - 1 midi = (mini + maxi) // 2 y += 1 if mini > maxi: print("Нет такого слова в этой букве!") print(txt2.format(y)) else: place = midi print(txt.format(place)) print(txt2.format(y))