Запрещенный элемент поиска в реализациях двоичного поиска Python - PullRequest
Новая
       27

Запрещенный элемент поиска в реализациях двоичного поиска Python

0 голосов
/ 02 октября 2019

Я реализовал бинарный поиск в Python по-разному, и я проверял его по отсортированному списку. Итеративное решение терпит неудачу, когда элемент поиска выходит за границы минимальных и максимальных значений списка.

Я провел некоторое начальное тестирование и отладку. Я не могу понять проблему в реализации. 

def bisect_search_itr(L, e):
  low = 0
  high = len(L)
  mid_index = (low + high) // 2
  while low <= high:
    if L[mid_index] == e:
      return True
    else:
      if e > L[mid_index]:
        low = mid_index
      else:
        high = mid_index
    mid_index = (low + high) // 2
  return False

def bisect_search_rec(L, e):
  if L == []:
    return False
  elif len(L) == 1:
    return L[0] == e
  else:
    half = len(L) // 2
    if L[half] > e:
      return bisect_search_rec(L[:half], e)
    else:
      return bisect_search_rec(L[half:], e)

def bisect_search_rec_with_bounds(e, m, n):
  if m == n:
    return L[m] == e
  else:
    half = m+n//2
    if L[half] == e:
      return True
    else:
      if e < L[half]:
        return bisect_search_rec_with_bounds(e, m, half)
      else: 
        return bisect_search_rec_with_bounds(e, half, n)

# Test case
L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
x = 17

print(bisect_search_itr(L, x))
print(bisect_search_rec(L, x))
print(bisect_search_rec_with_bounds(x, 0, len(L) - 1))

У рекурсивных реализаций все в порядке, но для итеративной реализации она сталкивается с бесконечным циклом.

Ответы [ 2 ]

0 голосов
/ 02 октября 2019

Отладить эту проблему очень просто. Просто присоедините отладчик (или используйте операторы print), чтобы увидеть, что основная причина вашего бесконечного цикла заключается в том, что после определенной точки (когда low и high приближаются друг к другу`) ничего в вашем цикле не меняется.

Давайте рассмотрим очень упрощенный пример: L = [1, 2], x = 5. В этом случае low = 1, high = 2, mid_index = 1. Внутри цикла вы увидите, что элемент больше середины, поэтому вы установите low = mid_index в 1 и, наконец, mid_index в 1. Так что ничего не изменилось. Вы на самом деле не увеличивали ни low, ни mid_index, то есть бесконечный цикл. Для любого L, не содержащего x, после достаточного количества итераций вы найдете этот точный сценарий внутри цикла.

Чтобы устранить проблему, убедитесь, что для каждой итерации либо low, либо high изменения. Например, поскольку вы уже проверили, что элемент mid_index - это не то, что вы ищете, можно безопасно установить low в mid_index + 1.

0 голосов
/ 02 октября 2019

Ошибка заключается в строке while low <= high: и единственный выход из этого цикла - через L[mid_index] == e. В данных вашего примера целевой элемент отсутствует в списке. После нескольких итераций все low, high и mid_index будут находиться на самом высоком номере в списке.

В зависимости от того, как вы хотите реализовать это, вы можете либо вернуть ближайшее значение (15), либо броситьошибка, если low и high равны.

...