Вступление

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

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

Двоичный поиск - пример

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

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

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

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

{.ezlazyload}

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

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

{.ezlazyload}

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

• мы нашли x , если нет - x вообще не существует в массиве.

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

Чтобы быть более точным, количество элементов, которые нам нужно проверить в худшем случае, равно log ~2~ 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 , мы вам поможем!