Реализация алгоритма двоичного поиска

Question

Я получаю индексную ошибку для большего набора данных, используя эту функцию двоичного поиска. Когда я вводим меньший набор данных, т. Е. [1,2,3,4,5], ищущий 5. алгоритм работает как ожидалось. Однако, когда я беру текст ниже, вызовите метод split для строкового объекта с нулевым списком параметров (delimeter char is '') и разбейте строку в значение списка, где каждый элемент является строкой, и выполните поиск слова ' кульпа»Я в конечном итоге со следующей ошибкой:

IndexError: список индексов вне диапазона

Помощь очень ценится. Спасибо.

string: 1. Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tem incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud, осуществляющий работу, выполняемый в соответствии с потребностями. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat не имеет отношения к делу, sunt in culpa qui officia deserunt mollit anim id est laborum.

код: http://ideone.com/TXVfQA

def binary_search(l,skey,start,stop): 
    length = (stop - start) + 1 # length of search space 
    middle = start + (length/2) 
    mid_val = l[middle] 
    if skey == mid_val: 
     return middle 
    elif skey > middle: 
     return binary_search(l,skey,(middle + 1),stop) 
    else: 
     return binary_search(l,skey,start,(middle - 1)) 

Answer 1

Существует несколько проблем с этим алгоритмом.

Во-первых, если вы запрашиваете элемент, меньший, чем самый маленький в списке (skey < l[start]), то он петли. Во-вторых, когда skey not in l[start:stop], тогда поиск падает с индексом за пределы.

У вас нет подходящего поведения для случая, когда элемент не представлен в списке. Например, вы можете вернуть None, если элемент не найден. Ваш код может быть исправлен таким образом:

def binary_search(l, skey, start, stop): 
    # possible answer is always in interval [start, stop) 
    while start + 1 != stop: 
     middle = (start + stop) // 2 
     mid_val = l[middle] 
     if skey < mid_val: 
      stop = middle 
     else: 
      start = middle 
    return start if l[start] == skey else None 

Это будет найти последнее вхождение элемента равного skey. Он также использует цикл вместо рекурсии, экономя время, необходимое для выполнения функции.

Answer 2

Вы никогда не проверять, если stop меньше start. Ваши рекурсивные вызовы легко создадут это условие.