бинарный поиск в питона странное поведение

Question

Пожалуйста, посмотрите на этот код:

def chop(array, search): 
     lo = 0 
     high = len(array) - 1 
     while lo <= high: 
       mid = (high + lo) /2 
       if array[mid] == search: 
         return 'true' 
       elif search > array[mid]: 
         low = mid + 1 
       else: 
         high = mid - 1 
     return 'false' 



if __name__ == '__main__': 
     a = [1,2,3,4,5,6,7,8,9,10] 
     print chop(a, 3) 

я написал небольшой скрипт, который, как предполагается, для поиска числа в массиве - регулярный бинарный поиск. Поэтому я запускаю скрипт, и, например, когда я помещаю chop(a, 1), я получаю истинное значение, когда я помещаю chop(a, 2). Я получаю истинное значение, но когда я помещаю chop(a, 3), я не получаю ответ, просто пустую строку в оболочке Python.

Есть ли у кого-нибудь идеи о том, что происходит?

Answer 1

Я предполагаю, что это ваша ошибка:

low = mid + 1 

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

Изменение этой строки:

lo = mid + 1 

и ваш алгоритм должен работать.