Двоичный поиск с использованием рекурсии переходит в бесконечный цикл

Я новичок в python, поэтому не знаю, отсутствует ли я что-то очевидное (например, двоеточие или какой-то период).Двоичный поиск с использованием рекурсии переходит в бесконечный цикл

Я пытаюсь выполнить этот алгоритм бинарного поиска, но если я пройду список, превышающий 3 элемента, программа перейдет в бесконечное торможение рекурсии и максимум, установленный в python.

базовые шкафы работа хорошо.

[] и [element1] списки проходят.

[element1, element2, element3, ..., element99] застревают ...

Вот код:

def binsearch(pylist, element): 
    if len(pylist) == 0: 
     return False 
    elif len(pylist) == 1 and pylist[0] == element: 
     return True 
    else: 
     mid = len(pylist)/2 - 1 
     if element > pylist[mid]: 
      binsearch(pylist[mid:], element) 
     else: 
      binsearch(pylist[:mid], element)

Спасибо.

источник

2016-12-22 David Simon Tetruashvili

Это, вероятно, может помочь вам: https://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html – iFlo

Подумайте о том, что произойдет, если вы запустите 'binsearch ([1], 2)'. –

Ничего очевидно для меня. В большинстве случаев интерпретатор Python будет диагностировать недостатки, подобные тем, которые вы упоминаете в любом случае (но не всегда, конечно). Совет. Приобретите среду разработки (IDE), которая позволяет установить точки останова, чтобы вы могли проверить содержимое переменных в своей программе или просто поместить временные инструкции * print *, чтобы вы могли найти, где ваши рассуждения прошли неправильно. –

Мы, очевидно, должны предположить, что данные отсортированы, в противном случае двоичный поиск довольно бессмыслен. Во-первых, вы не досчитались случай, когда элемент равен сам стержень:

if element == pylist[mid]:

Кроме того, в этом блоке:

elif len(pylist) == 1 and pylist[0] == element: 
    return True

Вы не обрабатывать случай, когда вы один элемент влево и это не элемент, который вы хотите, и в этом случае вы должны вернуть False.

Ниже полностью исправленный код:

def binsearch(pylist, element): 
    pylist = sorted(pylist) # Just to be sure 
    if len(pylist) == 0: 
     return False  

    if len(pylist) == 1: 
     if pylist[0] == element: 
      return True 
     else: 
      return False 
    else: 
     mid = len(pylist) // 2 
     if element == pylist[mid]: 
      return True 
     elif element > pylist[mid]: 
      return binsearch(pylist[mid:], element) 
     else: 
      return binsearch(pylist[:mid], element)

Существует, конечно, комната, чтобы сделать этот код более эффективным, но это просто исправление кода, как это было дано.

источник

2016-12-22 13:27:07

Хорошо сделано. Пришлось сделать функцию сортировки пузырьков для сортировки случайного списка без функции set().

def binsearch(pylist, element): 
    if len(pylist) == 0: 
     return False 
    else: 
     v_mid = len(pylist) // 2 
     if pylist[v_mid] == element: 
      return True 
     else: 
      if element > pylist[v_mid]: 
       return binsearch(pylist[v_mid + 1:], element) 
      else: 
       return binsearch(pylist[:v_mid], element)

источник

2016-12-22 15:14:14

Двоичный поиск с использованием рекурсии переходит в бесконечный цикл

ответ

Смежные вопросы