Поиск в массиве делением пополам

В упорядоченных массивах поиск методом деления пополам - очень эффективен

def bisect_search_in_sorted(somelist,value):
    left, right = 0, len(somelist)
    while left<right:
        middle = (left+right)//2
        if somelist[middle]==value:
            return middle
        elif somelist[middle]<value:
            left=middle+1
        else:
            right=middle

a=[2,3,4,5,6,6,7,7,7,8,9]
print bisect_search_in_sorted(a,7)

Подобную функцию можно использовать для поиска "правильного" индекса
и последующей вставки нового элемента в массив. Т.е. из такой функции легко
сделать хэш-фукнцию и создать эффективный упорядоченный список.