0

Попытался написать алгоритм нахождения бинарного поиска, получилось очень криво, конечно, в целом алгоритм работает нормально. правильно, но иногда происходит бесконечный цикл, почему это происходит не могу понять.. Если вписать 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)
1

2 ответа 2

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)
5
  • @Namerek, не утерпел я - переписал код полностью на базе найденного метода в инете:-) Спасибо за комментарии. Меня тоже сильно подивил код исходный. 15 мая 2022 в 9:45
  • @Nekto a, если ответ был полезным, его можно отметить плюсом (нажать треугольник вверх слева от вопроса). Если ответ полностью решил задачу - принять ответ (нажать на галку под треугольниками слева). 15 мая 2022 в 10:14
  • 1
    Я вам больше скажу, меня Ваш код тоже подивил. Опуская общее разногласие в определениях бинарного поиска, хочу заметить ... colab.research.google.com/drive/…
    – Namerek
    15 мая 2022 в 11:25
  • @Namerek, этот кусок с загадочным rando - не мой код:-) Это кусок автора, оставил его так как он не мешал. "Мой" (=чужой адаптированный:-) начинается с комментария "Ниже нормальный простой рабочий алгоритм". 15 мая 2022 в 11:40
  • Сергей, спасибо большое!
    – Nekto a
    15 мая 2022 в 12:58
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'
)

2
  • красиво, но сложновато для понимания. 15 мая 2022 в 10:03
  • @Namerek, спасибо большое!
    – Nekto a
    15 мая 2022 в 12:59

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.