Python:алгоритм бинарного поиска

Идея этого алгоритма проста(работает на отсортированных массивах\списках):

Сначала высчитываем индекс среднего элемента по формуле (m+n)//2.Где n это индекс начального элемента, а m количество элементов в массиве  В случае нечетного числа элементов округляем до ближайшего целого полученный результат. А дальше уже смотрим  что получается:

а) Элемент найден и мы возвращаем его индекс 

б) Средний элемент меньше ключа поиска 

в) Средний элемент больше ключа поиска 

В случае б) мы должны отсечь те элементы которые меньше среднего, то есть правую часть массива\списка. Дробится этого можно приняв за начальную границу поиска первый элемент со значением больше чем средний элемент, а у нас массив\список сортированный значит это элемент с индексом  i+1, где  i индекс среднего элемента. а конечная граница поиска последний элемент. в случае в) нам нужно принять за начальную границу первый элемент меньший среднего, а значит нам нужен элемент с индексом i-1.  Как конечная граница поиска естественно принять индекс первого элемента. Итак весь процесс будем повторять пока не выполниться любое из трех условий:

1) Элемент найден 

2) Начальная граница стала равна наибольшему элементу массива

3) Начальная граница стала равна индексу наименьшего элемента.
Самый положительный для нас случай 1.Преимущество алгоритма в том что при каждом сравнении убавляется половина отрезка, где происходит поиск элементов.
Краткое описание алгоритма:
1. Взять  индекс первого  элемента (n)
2. Взять индекс конечного элемента (длину массива ) (m)
3. Рассчитать индекс среднего элемента по формуле (m+n)\2 (i)
4. Сравнить средний элемент с ключом
4a Пока 0<=i
5а Если ключ = =элементу в выходим из программы
5б Если ключ>элементу,то n=i+1 m=len(l)
5в Если ключ<элементу, то n=i m=i-1  
6. Переходим к шагу 4a      
А вот и код на python,реализующий алгоритм:
def  quick_sort(l,k):
    m=len(l)
    n=0
    i=(m+n)//2
    while 0<=i
        if l[i]==k:
            return i
        elif  l[i]
            m=len(l)
            n=i+1
        elif  l[i]>k:
            m=i-1
            n=i
        i=(m+n)//2  
    return None  

Python: списки

Обойти вниманием такой тип данных языка Python нельзя.
Списки это последовательность элементов. Данный тип данных относится к изменяемым. Фактически список это структура данных которая реализует хорошол известную структуру данных в программировании: связный список.
Список как структура данных Python поддерживает следующие операции:
append (a)--вставка элемента любого типа в конец списка    
extended(a)--присоединяет в конец  списка другой список переданный параметром функции
count(a)--подсчитывает количество элементов c значением a
index(a)--возвращает индекс искомого элемента или возбуждает исключение ValueError
insert(i,a)--вставить объект  a произвольного типа в позицию i
remove(a)--удаляем элемент со значением a
pop()--удаляем у списка последний элемент и считываем его в переменную имитируя поведение стека.
reverse-переворачивает список, т.е. первый элемент меняется местами с последним и т.д.
sort-сортируем список
Еще список позволяет брать срезы:
a=range(10)#генерируем список из 10 значений от 0 до 10(исключая 10)

 a[1:5]#берем срез с 1 по 5 элемент
[1, 2, 3, 4]
 a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Обратим внимание что первый элемент имеет индекс 0, а не 1!
Кроме того мы можем брать срезы с определенным шагом:
 a[1:5:2]#выбираем каждый второй элемент начиная с 1-го и до 5-го
[1, 3]
А если хотим получить весь список:
 a[:]#выбираем все элементы списка
Все элементы начиная с 1-го
 a[1:]#выбираем все элементы списка начиная с 1(по умолчанию шаг 1)
 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Все элементы с шагом 2:
 a[::2]
[0, 2, 4, 6, 8]
Но Python предоставляет нам дзен-возможности: отрицательные индексы:)
выберем последний элемент:
a[-1]
9
А такой срез нам даст пред предпоследний и предпоследний:
a[-3:-1]
[7, 8]
Ну и весь список в обратном порядке:

a[::-1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Пара слов о срезах. Срезы это общий инструмент для всех последовательностей. Срез это независимый объект от первоначального, точнее копия выбранной части. Проверим это:
a=range(10)
asl=a[0:3]
for i in xrange(0,len(asl)): #здесь применена функция xrange, которая возвращает нам #итератор по объекту xrange. Хrange генерирует цифру только во время обращения, чем #экономится память и время выполнения
asl[i]=asl[i]*3

asl
[0, 9, 6]

a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Как видим изменения внесенные в срез никоим образом не затронули исходный объект.
А вот если мы присвоим двум переменным одинаковый список таким образом:

 a=b=range(10)
 a[1]=a[1]*10
 a[1]
10
 a
[0, 10, 2, 3, 4, 5, 6, 7, 8, 9]
 b
[0, 10, 2, 3, 4, 5, 6, 7, 8, 9]
Этот интересный результат связан с тем что в данном случае произошло так называемое поверхностное копирование объектов. Так как в python все переменные это на самом деле ссылки, то когда python обрабатывает присвоения вида: a=b=4 то он прост связывает с именами a и b одну и ту же ссылку
А если мы напишем так:  


a=range(10)
b=range(10)
a[1]=a[1]*10
a
[0, 10, 2, 3, 4, 5, 6, 7, 8, 9]
b
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


 То все стандартно так как Python свяжет с каждым именем свою собственную ссылку.
В список можно вкладывать списки и любые другие объекты. Наиболее быстрые операции это pop и append, а вставка элементов и их удаление из середины займут больше времени из за перенастройки указателей в списке.