Почему я получаю индекс индекса вне диапазона в моем коде?

Question

Ошибка возникает в линии if data[l][0] == value:

def binary_pairs(data, value): 
    l = 0 
    h = len(data) - 1 
    while l < h and data[l]!= value: 
     m = (h + l) // 2 
     if data[m][0] == value: 
      l = m 
     elif data[m][0] < value: 
      l = m + 1 
     else: 
      h = m - 1 
    print("done") 
    if data[l][0] == value: 
     return l 
    else: 
     return -1 

Пример ввод: [[ "мертвый", [ "brian.txt", "grail.txt"]], [ " eunt", [ "Брайан. .txt "]], [ "отшлепать", [" grail.txt "]] ]

Answer 1

Я вижу два возможных проблем с вашим кодом:

• Это кажется странным, что вы используете как data[l] и data[l][0] в сравнении.

• Если, например, l==0 и h==1 и вы в конечном итоге принимает else (h = m - 1), вы бы в конечном итоге с h==-1, что выходит за пределы. Могут быть другие подобные проблемы.

Answer 2

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

• Если вы пытаетесь решить проблему, а не пытаться научиться писать бинарный поиск, рекомендуется использовать bisect модуль Питона.

http://docs.python.org/2/library/bisect.html

• Это лучшая практика в Python, чтобы соответствовать стандарту кодирования под названием PEP 8; это не рекомендует использовать в нижнем регистре L в качестве имени переменного или верхнего регистра И.

http://www.python.org/dev/peps/pep-0008/

• Было бы чище, чтобы иметь петлю немедленно возвращает индекс, когда он обнаруживает, что значение , вместо того, чтобы проверить цикл в верхней части, чтобы убедиться, что значение еще не найдено, что приведет к завершению цикла, а затем значение, которое будет возвращено из нижней части функции. Если цикл завершается, вы можете вернуть -1 в конце функции.

• Ваша петля проверяет, что индекс равен < h, но не проверяет, что индекс I >= 0. Я подозреваю, что это может быть вашей проблемой.

• При отладке цикла, подобного этому, часто бывает полезно добавлять операторы печати, которые регистрируют то, что происходит. Вы должны напечатать значение индекса и напечатать достаточно других строк, чтобы узнать, увеличивается ли оно или уменьшается, и насколько.