Блог

Главная - Вопросы по программированию - Двоичный поисковый код продолжает выдавать ошибку вне диапазона

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

#python #binary-search

Вопрос:

При двоичном поиске я постоянно сталкиваюсь с ошибкой, что индекс в моем коде: «mid», остается вне диапазона. Есть ли какой-нибудь способ это исправить? Код:

 def binary_search(num, key):
  low = 0
  high = len(num)
  while high >= low:
    mid = (low   high)//2
    if num[mid] < key:
      low = mid   1
    elif num[mid] > key:
      low = mid   1
    else:
      return mid
  return -1
A = [2, 4, 7, 10, 11, 32, 45, 87, 90]
print(binary_search(A, 10))

Ответ №1:

ваши условия испорчены, понимаете

 def binary_search(num, key):
  low = 0
  high = len(num)
  while high >= low:
    mid = (low   high)//2
    if num[mid] < key:
      low = mid   1
    elif num[mid] > key:
      high = mid - 1
    else:
      return mid
  return -1
A = [2, 4, 7, 10, 11, 32, 45, 87, 90]
print(binary_search(A, 10))

*внутри elif

Ответ №2:

Проблемы в вашем коде:

  • Вы каждый раз меняетесь только low в своем коде. high остается неизменным.
  • Когда num[mid] > key тогда ключ лежит слева от mid . Так high = mid - 1 .

Это должно быть правильной реализацией.

 def binary_search(num, key):
  low = 0
  high = len(num)-1
  while high >= low:
    mid = (low   high)//2
    if num[mid] < key:
      low = mid   1
    elif num[mid] > key:
      high = mid - 1
    else:
      return mid
  return -1
A = [2, 4, 7, 10, 11, 32, 45, 87, 90]
print(binary_search(A, 11))
Метки: