Это работает, потому что mid
всегда находится в правильном диапазоне, но это линейный поиск, а не двоичный. Вы можете проверить это, напечатав изучаемые индексы:
def binary_search(list, item):
low = 0
high = len(list)-1 #sets upper range to length of provided list
while low <= high:
mid = (low + high) #why does (low + high) give me middle of list?
print("mid =", mid)
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
Ищите -1 в вашем примере:
>>> print (binary_search([1,3,5,7,9],-1))
mid = 4
mid = 3
mid = 2
mid = 1
mid = 0
None
Итак, вы правы: вы должны разделить mid
на 2 (и избегайте использования list
в качестве имени переменной).
Вероятно, есть лучшее решение. Но это работает:
]
как в:
<blah value="]"></blah>
затем снова, так же (см. Ответ Киртана):
<blah value="]"></blah>
Квадратные скобки не нуждаются в особой нотации в XML, но имеют особое значение при использовании в выражениях XPath для преобразований XSL.
<root>
<el attrib="[">[</el>
</root>