Бинарный поиск в Python

Вступление

В этой статье мы погрузимся в идею и реализацию Python Binary Search .

Бинарный поиск-это эффективный алгоритм поиска, который работает с отсортированными массивами. Он часто используется как один из первых примеров алгоритмов, работающих в логарифмическом времени ( O(logn) ) из-за его интуитивного поведения и является фундаментальным алгоритмом в информатике.

Бинарный поиск – Пример

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

Если целевой элемент больше среднего элемента – он не может быть расположен в первой половине коллекции, поэтому он отбрасывается. То же самое происходит и наоборот.

Примечание: Если массив имеет четное число элементов, то не имеет значения, с какого из двух “средних” элементов мы начнем.

Давайте быстро рассмотрим пример, прежде чем мы продолжим объяснять, как работает бинарный поиск:

Как мы видим, мы точно знаем, что, поскольку массив отсортирован, x не находится в первой половине исходного массива.

Когда мы знаем, в какой половине исходного массива находится x , мы можем повторить этот точный процесс с этой половиной и снова разделить ее на половинки, отбросив половину, которая наверняка не содержит x :

Мы повторяем этот процесс до тех пор, пока не получим подмассив, содержащий только один элемент. Мы проверяем, является ли этот элемент x . Если это так – мы нашли x , если это не так – x вообще не существует в массиве.

Если вы присмотритесь к этому поближе, то заметите, что в худшем случае ( x не существует в массиве) нам нужно проверить гораздо меньшее количество элементов , чем в несортированном массиве, что потребует чего-то большего в духе Линейного поиска , что безумно неэффективно.

Если быть более точным, то количество элементов, которые нам нужно проверить в худшем случае, равно log ₂ N где N – количество элементов в массиве.

Это оказывает тем большее влияние, чем больше массив:

Если бы наш массив состоял из 10 элементов, нам нужно было бы проверить только 3 элемента, чтобы либо найти x , либо сделать вывод, что его там нет. Это 33,3%.

Однако, если бы в нашем массиве было 10 000 000 элементов, нам нужно было бы проверить только 24 элемента. Это 0,0002%.

Реализация Бинарного Поиска

Двоичный поиск-это естественно рекурсивный алгоритм, поскольку один и тот же процесс повторяется на все меньших и меньших массивах до тех пор, пока не будет найден массив размером 1. Однако, конечно, существует и итеративная реализация, и мы покажем оба подхода.

Рекурсивный

Давайте начнем с рекурсивной реализации, так как это более естественно:

def binary_search_recursive(array, element, start, end):
    if start > end:
        return -1

    mid = (start + end) // 2
    if element == array[mid]:
        return mid

    if element < array[mid]:
        return binary_search_recursive(array, element, start, mid-1)
    else:
        return binary_search_recursive(array, element, mid+1, end)

Давайте подробнее рассмотрим этот код. Мы выходим из рекурсии, если элемент start выше элемента end :

if start > end:
        return -1

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

В этот момент start равно end . Однако, поскольку element не равен array[mid] , мы снова “разбиваем” массив таким образом, что либо уменьшаем end на 1, либо увеличиваем start на единицу, и рекурсия существует при этом условии.

Мы могли бы сделать это, используя другой подход:

if len(array) == 1:
    if element == array[mid]:
        return mid
    else:
        return -1

Остальная часть кода выполняет логику “проверить средний элемент, продолжить поиск в соответствующей половине массива”. Мы находим индекс среднего элемента и проверяем, соответствует ли ему искомый элемент:

mid = (start + end) // 2
if elem == array[mid]:
    return mid

Если это не так, мы проверяем, является ли элемент меньше или больше среднего элемента:

if element < array[mid]:
    # Continue the search in the left half
    return binary_search_recursive(array, element, start, mid-1)
else:
    # Continue the search in the right half
    return binary_search_recursive(array, element, mid+1, end)

Давайте продолжим и запустим этот алгоритм с небольшой модификацией, чтобы он распечатал, над каким подмассивом он работает в данный момент:

element = 18
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]

print("Searching for {}".format(element))
print("Index of {}: {}".format(element, binary_search_recursive(array, element, 0, len(array))))

Запуск этого кода приведет к:

Searching for 18
Subarray in step 0:[1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1:[16, 18, 24, 28, 29]
Subarray in step 2:[16, 18]
Subarray in step 3:[18]
Index of 18: 7

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

Searching for 20
Subarray in step 0: [4, 14, 16, 17, 19, 21, 24, 28, 30, 35, 36, 38, 39, 40, 41, 43]
Subarray in step 1: [4, 14, 16, 17, 19, 21, 24, 28]
Subarray in step 2: [19, 21, 24, 28]
Subarray in step 3: [19]
Index of 20: -1

И просто для удовольствия мы можем попробовать поискать некоторые большие массивы и посмотреть, сколько шагов требуется двоичному поиску, чтобы выяснить, существует ли число:

Searching for 421, in an array with 200 elements
Search finished in 6 steps. Index of 421: 169

Searching for 1800, in an array with 1500 elements
Search finished in 11 steps. Index of 1800: -1

Searching for 3101, in an array with 3000 elements
Search finished in 8 steps. Index of 3101: 1551

Повторяющийся

Итеративный подход очень прост и похож на рекурсивный. Здесь мы просто выполняем проверки в цикле while :

def binary_search_iterative(array, element):
    mid = 0
    start = 0
    end = len(array)
    step = 0

    while (start <= end):
        print("Subarray in step {}: {}".format(step, str(array[start:end+1])))
        step = step+1
        mid = (start + end) // 2

        if element == array[mid]:
            return mid

        if element < array[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return -1

Давайте заполняем массив и ищем в нем элемент:

array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]       

print("Searching for {} in {}".format(element, array))
print("Index of {}: {}".format(element, binary_search_iterative(array, element)))

Запуск этого кода дает нам результат:

Searching for 18 in [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 0: [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29]
Subarray in step 1: [16, 18, 24, 28, 29]
Subarray in step 2: [16, 18]
Subarray in step 3: [18]
Index of 18: 7

Вывод

Двоичный поиск-это невероятный алгоритм, который можно использовать на больших отсортированных массивах или всякий раз, когда мы планируем многократно искать элементы в одном массиве.

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

Если мы сортируем массив и ищем элемент только один раз, то более эффективно просто выполнить линейный поиск по несортированному массиву.

Если вы хотите прочитать об алгоритмах сортировки в Python , мы вас накроем!