Ошибка при бинарном поиске

Question

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


import random

#Рандом можно использовать, я добавил да бы постоянно не прописывать разные наборы чисел. В данный момент, он бесполезен. 
def rando(r):
    while r <= 200:
        rand = random.randint(1, 25)
        r = random.randrange(chisla[-1], chisla[-1] + rand)
        if r in chisla:
            continue
        else:
            chisla.append(r)
    return chisla


chisla = [0, 1, 13, 21, 33, 40, 49, 53, 55, 63, 67, 68, 70, 80, 83, 89, 98, 104, 119, 132, 140, 142, 153, 173, 176,
          186, 188, 192, 195, 199, 200, 201]
r = 1
#rando(r)
print(len(chisla))
print(chisla)
print('Введите число, номер которого вы хотите узнать:')
#Если в переменную ниже ввести число 186, то будет бесконечный цикл, если другое  число то цикла нет...
Nuj_Chislo = int(input()) #Ввод числа, порядковый номер которого хотим узнать.
i = int()
a = 1
if len(chisla) / 2 != 0: # Этот if для проверки на четность или не четность длины списка.
    a = int((len(chisla) + a) / 2) #Нахождение индекса числа середины списка.
if Nuj_Chislo > chisla[a]: # Здесь происходит проверка, если нужное число больше чем индекс числа находящийся в середине списка.
    c = len(chisla)
    a = int(c / 2)
    while chisla[a] != Nuj_Chislo: 
        if Nuj_Chislo > chisla[a]: #Проверка больше ли число, проверка чисел в половины, и дальше четверти, 1/8.. и т.д.
            i = a
            a = int((len(chisla) + i) / 2)#Проверка меньше ли число, проверка чисел в половины, и дальше четверти, 1/8.. и т.д.
        elif Nuj_Chislo < chisla[a]:
            a = int((i + 1) / 2)
            i = a
elif Nuj_Chislo < chisla[a]:# Здесь происходит проверка, если нужное число меньше чем индекс числа находящийся в середине списка.
    a = int((a + 1) / 2)
    while chisla[a] != Nuj_Chislo:
        if Nuj_Chislo > chisla[a]:
            a = int((len(chisla) + i) / 2)
            i = a
        elif Nuj_Chislo < chisla[a]:
            i = a
            a = int((i + 1) / 2)
print(a)

Answer 1

Поправьте меня если не прав, но я себе бинарный поиск как-то так представлял.
(Ну схематически по крайней мере)

from random import randrange
from typing import List

u_bound = 2000
l_bound = 0
value_list = [*range(l_bound, u_bound + 1)]
hidden = randrange(l_bound, u_bound + 1)

print(f'Загадано число {hidden}.')


def split_list(val: List[int], test: int, iter_count=0):
    iter_count += 1
    if len(val) == 1:
        return val[0], iter_count

    middle = len(val) // 2

    left, right = val[:middle], val[middle:]

    return split_list(
        left if test in left else right,
        test,
        iter_count
    )


item, attempts = split_list(
    value_list, hidden
)
print(
    f'Угадано число: {item}',
    f'За {attempts} попыток',
    sep='\n'
)

Answer 2

С середины кода я вставил простую реализацию. проверил для 186 - прекрасно работает. Сравните со своим кодом, поймите, почему у вас он такой громоздкий. На будущее - видите, что ваш код принимает странный вид - либо думайте сами, либо ищите в интернете, всё ли у вас правильно с алгоритмом или с методом реализации алгоритма. Простота реализации должна быть ведущим принципом.

import random

def rando(r):
    while r <= 200:
        rand = random.randint(1, 25)
        r = random.randrange(chisla[-1], chisla[-1] + rand)
        if r in chisla:
            continue
        else:
            chisla.append(r)
    return chisla


chisla = [0, 1, 13, 21, 33, 40, 49, 53, 55, 63, 67, 68, 70, 80, 83, 89, 98, 104, 119, 132, 140, 142, 153, 173, 176,
          186, 188, 192, 195, 199, 200, 201]
r = 1
rando(r)
print(len(chisla))
print(chisla)
print('Введите число, номер которого вы хотите узнать:')
#Если в переменную ниже ввести число 186, то будет бесконечный цикл, если другое  число то цикла нет...
Nuj_Chislo = int(input())

# Ниже нормальный простой рабочий алгоритм
mid = len(chisla)//2
low = 0
high = len(chisla) - 1

while chisla[mid] != Nuj_Chislo and low <= high:
    if Nuj_Chislo > chisla[mid]:
        low = mid + 1
    else:
        high = mid - 1
    mid = (low + high) // 2

if low > high:
    print("Нет числа")
else:
    print("номер:", mid)

БЛОГ НА HUSL

Ошибка при бинарном поиске

Ответы (2 шт):