bin_search.md

#Бинарный поиск

Про бинарный поиск можно говорить очень долго, так как этот алгоритм несмотря на свою простоту обладает поистине мощным применением, и сама идея, лежащая в основе, тоже является незаменимой в багаже знаний любого программиста.

Начнем мы с небольшого описания алгоритма. Суть бинарного поиска в том, что мы делим какое-то множество на две примерно равные части и, анализируя элемент по середине, отбрасываем либо первую, либо вторую половину, далее продолжаем поиск рекурсивно в выбранной части множества. Уже можно догадаться, что алгоритм работает только тогда, когда можно выбрать этот "средний" элемент - тем самым необходима, например, упорядоченность рассматриваемого множества. Чтобы разобраться лучше, сейчас мы рассмотрим несколько задач, для которых бинарный поиск крайне эффективен, а иногда является единственным решением.

###Поиск элемента в массиве

Пусть нам дан упорядоченный массив, который в процессе не будет изменяться. И допустим, к нему приходит множество запросов на проверку того, что лежит ли какой-то элемент массиве или нет. Эту задачу мы решим с помощью бинарного поиска, который намного быстрее обычного линейного поиска, работающего в худшем случае за $$O(n)$$.

Итак, суть все та же - выбираем средний элемент в массиве, сравниваем его с нужным элементом и отбрасываем либо левую часть массива, либо правую, потом запускаем ту же процедуру над нужной половиной. В конце мы придем к массиву длинной 1, и нам останется проверить только равенство этого одного элемента с данным. Приведем главную часть кода:

# массив array отсортирован по возрастанию
def bin_search(array, elem):
    # если массив пустой, то никакого элемента там точно нет
	if len(array) < 1:                      
	    return False                        
		
	# самый простой случай - массив состоит из одного элемента
	# сравниваем этот элемент с нужным
	if len(array) == 1:                      
	    return array[0] == elem            
	                                        
	# тут идет выбор "среднего"	
	m = len(array) // 2                     
	
	# если мы уже нашли элемент, то почему бы сразу не понять это
	if array[m] == elem:                   
	    return True      
	
	# сравниваем "средний" элемент с данным
    # и понимаем какую половину массива следует нам отбросить
	if array[m] < elem:
	    # если "средний" элемент меньше нужного, мы отбрасываем левую половину 
        # так как все элементы в ней заведомо меньше
	    return bin_search(array[m + 1:], elem)
	else:
	    # аналогично для правой, где все элементы больше
		return bin_search(array[:m], elem)  
		                                    

Эту рекурсию естественным образом можно переписать в цикл, который будет работать оптимальнее по времени и памяти.

# массив опять отсортирован по возрастанию
def bin_search(array, elem):
    # теперь мы будем поддерживать отрезок индексов [l, r),
    # в котором должен быть нужный элемент
    # если элемент есть в массиве, то он точно будет в этом отрезке
    l = 0                       
    r = len(array)              
                
    # если отрезок с самого начала пустой, то нашего элемента там точно нет    
    if r == 0:                  
        return False      
        
    # сужаем наш отрезок, пока не останется один элемент
    while l <= r:
        # как обычно выбираем "средний" элемент и сравниваем его с нужным
        m = (l + r) / 2
        
        # если средний элемент меньше, отбрасываем левую половину
        # сдвигая левый конец отрезка l в середину m
        if array[m] <= elem: 
            l = m
        else:
            # аналогично, сдвигаем правый конце в середину
            # отбрасывая правую половину
            r = m 
            
    # и в конце проверяем содержит ли наш отрезок нужный элемент
    return array[l] == elem     

Настало время исследовать скорость работы данного алгоритма. Допустим мы запускаем поиск на массиве длины $$n$$. Как уже говорилось ранее, каждая итерация бинарного поиска отбрасывает половину рассматриваемого массива, то есть после первого шага длина массива, в котором осуществляется поиск, будет равной $$n/2$$, после второго - $$n/2^2$$ ... после k-ого шага - $$n/2^k$$ (Мы используем целочисленное деление, которое отбрасывает остаток. Эта небольшая погрешностью не повлияет на конечную оценку. К тому же, все это можно доказать строже, но я и не стремлюсь к этому. Просто для понимания, почему так и не иначе, такого объяснения вполне достаточно.) В конце наш алгоритм должен сойтись к одному элементу, если это произошло на итерации $$k$$, то $$n/2^k = 1$$ и $$n = 2^k$$, то есть $$k = \log_2(n)$$. В итоге сложность алгоритма будет $$O(\log_2(n))$$, учитывая константу от целочисленного деления и других операций на каждом шаге.

###Поиск значения функции на отрезке

Перейдем теперь к следующей задаче, в которой бинарный поиск по-настоящему незаменим. Рассмотрим монотонную функцию (для простоты она будет возрастать) на каком-нибудь отрезке, и опять требуется искать на этом отрезке определенные значения.

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

# (l, r) - отрезок на котором нужно найти такое x, что f(x) = y
def bin_search(l, r, f, y):
    # задаем нужную точность ответа
    eps = 1e-10
    
    # ответ точно лежит, между l и r, если разница между ними станет меньше eps,
    # то полученное нами число будет отличатся от ответа не больше чем на eps
    while abs(r - l) > eps:
        # как обычно делим отрезок пополам и сравниваем середину с x, 
        # отбрасывая ненужную половину
        m = (r + l) / 2
        if f(m) < y:
            l = m
        else:
            r = m
    
    #возвращаем число внутри отрезка
    return (r + l) / 2

В данном случае асимптотика будет равна $$O(\log(\frac{R - L}{eps}))$$ ввиду того, что мы неявно разбиваем отрезок на $$\frac{R - L}{eps}$$ частей и ищем уже отрезок, который максимально подходит под условие задачи.