Бинарный поиск, python
Вот наштопал такой код
def binary_search(elem, sequence):
first_index = 0
last_index = len(sequence) - 1
mid_index = last_index / 2
found = False
while not found and first_index < last_index:
if sequence[mid_index] == elem:
found = True
elif sequence[mid_index] > elem:
last_index = mid_index
elif sequence[mid_index] < elem:
first_index = mid_index + 1
mid_index = (first_index + last_index) / 2
if sequence[last_index] == elem:
found = True
return found
def main():
size = 100000
for i in range(size):
if not binary_search(i, range(size)):
print i
if __name__ == '__main__':
print 'start'
main()
print 'end'
Гонял на разных размерах, вроде всё ок, кстати на 100000 - несколько минут работает, поэтому на больших не проверял.. .
но, вот, мне надо комбинации из букв сопоставлять из словарём, является ли это словом, в текстовом файле 127 000+ слов
И вот, некоторые слова не находит... .
В чём может быть прикол???
чёрт, форматирование сбилось, ёпта.. . надеюсь, питонисты разберутся )
Короче, алгоритм верен всё-таки, оказалось, что словарь в некоторых местах не отсортирован, теперь прямо сортирую словарь перед использованием )