Бинарный поиск встаёт посреди программы Pycharm
Реализовывал простую программу для сортировки массива данных, решил для удобства использовать бинарный поиск. Для маленького количества данных всё работало, как только количество элементов стало 21+, программа просто намертво встала, а в иных случаях вылетала ошибка "MemoryError: Stack overflow", помогите пожалуйста, в чем ошибка?
def binfound(x, a, low, hight):
mid = len(a) // 2
while low!=hight:
if x >= a[mid]:
low = mid + 1
else:
hight = mid - 1
mid = (low + hight) // 2
return mid+1 if x>=a[mid] else mid
b = [123,12,4,567,123,89876,543,765432,7654432543,7654,6543,8765432,654323,32,1,765432,6543,6543,765,432,554321,7654,54,432,4535874564456456,543,5,4332,65,432135,32,432,4321,654342,9,87876,76543,237654,321,765432,7654323,43445]
q = [0]
for i in b:
x = binfound(i, q, 0, len(q) - 1)
q = q[0:x] + [i] + q[x:]
print(q)
Ответы (3 шт):
Вообще специфичный код: у вас цикл по массиву b, в котором вы каждый элемент ищете в массиве q, который состоит из одного элемента 0. Может вы наоборот хотели?)
В самой функции тоже есть спорные моменты. Например условие, где вы сравниваете искомый элемент х с а[mid] на >=. Т.е. даже в случае если функция нашла элемент, цикл все равно сдвигает границу left за пределы найденного элемента индекса mid. Наверное стоит сделать принудительный выход из цикла, когда мы нашли элемент, т.е. добавить отдельную проверку в виде условия.
Также следует обратить внимание на строгое условие сравнения в цикле. Лучше обезопасить себя и написать left < height
low = 0
hight = 1
mid = 0
else: hight = mid - 1
high = -1
Это неправильно. Бинпоиск никогда не должен искать вне диапазона. Ну и зацикливается тоже из-за неё.
Кажется, должно быть
hight = mid
А ещё ошибка тут:
mid = len(a) // 2
Замена условия продолжения цикла на while low<hight: чинит ситуацию с зацикливанием. И вроде сортировка правильная получается при этом.