Что такое бинарный поиск в программировании
Перейти к содержимому

Что такое бинарный поиск в программировании

  • автор:

Двоичный, или бинарный, поиск элемента

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

При решении задачи на языке программирования Python вместо массива используется список

Описание алгоритма

  1. Находится средний элемент последовательности. Для этого первый и последний индексы связываются с переменными, а индекс среднего элемента вычисляется.
  2. Значение среднего элемента сравнивается с искомым значением. Если значение среднего элемента оказывается равным искомому, поиск завершается.
  3. Иначе, в зависимости от того, искомое значение больше или меньше значения среднего элемента, дальнейший поиск будет происходить только в левой или только в правой половинах массива.
  4. Для этого одна из границ исследуемой последовательности сдвигается. Если искомое значение больше значения среднего элемента, то нижняя граница сдвигается за средний элемент на один элемент справа. Если искомое значение меньше значения среднего элемента, то верхняя граница сдвигается на элемент перед средним.
  5. Снова находится средний элемент теперь уже в выбранной половине. Описанный выше алгоритм повторяется для данного среза.

Исходный код на Python

from random import randint # Создание списка, # его сортировка по возрастанию # и вывод на экран a = [] for i in range(10): a.append(randint(1, 50)) a.sort() print(a) # искомое число value = int(input()) mid = len(a) // 2 low = 0 high = len(a) - 1 while a[mid] != value and low  high: if value > a[mid]: low = mid + 1 else: high = mid - 1 mid = (low + high) // 2 if low > high: print("No value") else: print("ID =", mid)
[6, 17, 21, 27, 32, 35, 35, 36, 37, 48] 27 ID = 3
[4, 5, 12, 13, 13, 18, 22, 26, 30, 35] 28 No value

Другие варианты решения задачи двоичного поиска на Python:

from random import randint a = [randint(1, 50) for i in range(10)] a.sort() print(a) value = int(input()) left = 0 right = len(a) - 1 center = (left + right) // 2 while a[center] != value: if value > a[center]: left = center + 1 else: right = center - 1 center = (left + right) // 2 if left >= right: break if value == a[center]: print("ID =", center) else: print("No value") 
from random import randint a = [randint(1, 50) for i in range(10)] a.sort() print(a) value = int(input()) left = 0 right = len(a) - 1 while left  right: center = (left + right) // 2 if value == a[center]: print("ID =", center) break if value > a[center]: left = center + 1 else: right = center - 1 else: print("No value") 

Блок-схема алгоритма бинарного поиска

X Скрыть Наверх

Решение задач на Python

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

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

«IT-специалист с нуля» наш лучший курс для старта в IT

Принцип работы алгоритма бинарного поиска

Основная последовательность действий алгоритма выглядит так:

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

  1. Сортируем массив данных.
  2. Делим его пополам и находим середину.
  3. Сравниваем срединный элемент с заданным искомым элементом.
  4. Если искомое число больше среднего — продолжаем поиск в правой части массива (если он отсортирован по возрастанию): делим ее пополам, повторяя пункт 3. Если же заданное число меньше — алгоритм продолжит поиск в левой части массива, снова возвращаясь к пункту 3.

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

vsrat_7 1 (1)

Реализация бинарного поиска

Существуют два способа реализации бинарного поиска.

1. Итерационный метод. При таком подходе используется цикл, тело которого повторяется, пока не найдется заданный элемент либо не будет установлено, что его нет в массиве. Например, в Python для этой цели удобно использовать цикл while.

2. Рекурсивный подход. В этом случае пишется функция, которая вызывает сама себя (рекурсивно), пока не будет найден искомый элемент в массиве.

бинарный поиск позиции заданного элемента в списке

Приведем примеры реализации этих методов на Python.

Пусть есть массив чисел [5, 8, 9, 1, 23, 7, 3, 0, 15], и необходимо найти позицию числа 5 в упорядоченном списке. На вход такой функции необходимо подать уже отсортированный массив, для этого воспользуемся встроенным методом sorted(), который упорядочивает массив данных по возрастанию.

Код, использующий итерационный подход, будет выглядеть так:

def findPosition(num_list, number):
first = 0
last = len(num_list) - 1
while first middle = first + (last - first) // 2
if num_list[middle] == number:
return middle
elif num_list[middle] < number:
first = middle + 1
else:
last = middle - 1
return -1
num_list = sorted([5, 8, 9, 1, 23, 7, 3, 0, 15])
number = 5
print(findPosition(num_list, number))

При использовании рекурсивного поиска код на Python можно написать так:

def findPosition(num_list, number, first, last): if last >= first: middle = first + (last - first) // 2 if num_list[middle] == number: return middle elif num_list[middle] < number: return findPosition(num_list, number, middle + 1, last) else: return findPosition(num_list, number, first, middle - 1) else: return -1 num_list = sorted([5, 8, 9, 1, 23, 7, 3, 0, 15]) number = 5 print(findPosition(num_list, number, 0, len(num_list) - 1))

Начните карьеру в Data Science.
Онлайн-магистратура МФТИ с практикой на реальных проектах

В некоторых языках программирования, включая Python, есть готовые функции для выполнения бинарного поиска. Модуль бинарного поиска называется bisect. Проиллюстрируем его работу на примере:

from bisect import bisect_left def findPosition(num_list, number): pos = bisect_left(num_list, number) if pos < len(num_list): return pos return False num_list = sorted([5, 8, 9, 1, 23, 7, 3, 0, 15]) number = 5 print(findPosition(num_list, number))

Читайте также Как выбрать IT-специальность в новых реалиях?

В каких случаях используют бинарный поиск

Двоичный поиск подходит для нахождения позиций элемента в упорядоченном списке: в этом случае он эффективнее линейного, поскольку массив данных на каждом шаге разделяется надвое и одна половина сразу отбрасывается. Последовательная сложность двоичного метода в худшем и среднем случаях равна O(log n), в лучшем — O(1) (если обнаруживаем искомый элемент на первой итерации). Для сравнения: вычислительная сложность линейного поиска равна O(n) (обычный проход по всем элементам в поисках нужного).

У бинарного поиска есть недостаток — он требует упорядочивания данных по возрастанию. Сложность сортировки — не менее O(n log n). Поэтому, если список короткий, используется все-таки линейный поиск.

Разновидности алгоритма

На основе бинарного поиска разработано несколько дополнительных разновидностей поисковых алгоритмов:

  • однородный бинарный поиск, при котором аргумент поиска А сравнивается с ключом Ki, где i — золотое сечение интервала (оно выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка);
  • троичный поиск, когда интервал делится на три части вместо двух. Обычно применяется для поиска положения экстремума функции;
  • интерполирующий поиск, который предсказывает позицию нужного элемента на основе разницы значений. Эффективен, если элементы распределены достаточно равномерно;
  • дробный спуск — применяется для ускорения двоичного поиска в многомерных массивах данных, и другие.

Data Scientist

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

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

Задача. Загадано целое число $x$ от $1$ до $100$, которое вам нужно отгадать какой-нибудь «данеткой»: например, вы можете спрашивать, больше ли число $x$ чем заданное, или четно ли оно. За сколько вопросов в худшем случае вы сможете найти число $x$?

Одно из оптимальных решений имеет такую структуру: первым вопросом спрашиваем «больше ли число $x$, чем 50», и если ответ «да», то дальше спрашиваем «больше ли число $x$, чем 75», иначе «больше ли число $x$, чем 25», и повторяем дальше, каждый раз уменьшая отрезок возможных значений в два (или почти в два) раза.

Более структурно, если у нас есть отрезок поиска — изначально от $l=1$ до $r=100$ — то мы на каждой итерации выбираем «серединный» элемент $m = \lfloor \frac \rfloor$, спрашиваем «$x>m?$», выполняем присвоения $l = m + 1$ или $r = m$ в зависимости от ответа, и повторяем процедуру с новыми границами, пока они не станут равными (что будет означать, что $l = r = x$).

Вот пример такой программы, которую можно запустить в консоли:

  Если загадать $x=42$ и честно поотвечать на вопросы:
x > 50? no x > 25? yes x > 38? yes x > 44? no x > 41? yes x > 43? no x > 42? no x = 42 

Здесь нам потребовалось 7 вопросов, но в зависимости от загаданного числа иногда мы будем спрашивать ровно $7$ вопросов, а иногда $6$.

В общем случае, так как на каждой итерации длина отрезка поиска гарантированно уменьшится в два раза (возможно, с округлением вверх), то нам потребуется $O(\log n)$ операций, а точнее либо $\lceil \log_2 n \rceil$, либо $\lfloor \log_2 n \rfloor$.

#В структурах данных

Пусть дан массив $a$, и требуется определить, есть ли в нём элемент $x$.

Очевидно, в худшем случае этого элемента в массиве нет, но чтобы удостовериться в этом, нужно потратить $O(n)$ операций на просмотр всех элементов массива.

Однако, если массив отсортирован, найти число $x$ в массиве можно и быстрее: можно аналогичным способом найти нижнюю грань (англ. lower bound) — самое малое число, не меньшее $x$ — и проверить, оказалось ли оно равно $x$.

 Для стандартных контейнеров STL такая функция реализована:
Также в C++ есть функция upper_bound , которая находит первый элемент, который строго больше аргумента.

#Проверка свойств

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

Поиск нижней границы в массиве — частный случай: мы проверяем условие $(a[k] \geq x)$ и хотим найти, начиная с какого $k$ оно выполняется.

  • Найти последнее число, равное $x$ в отсортированном массиве, или вывести, что таких чисел нет.
  • Посчитать, сколько раз встречается число $x$ в отсортированном массиве.
  • Дан массив чисел, первая часть состоит из нечетных чисел, а вторая из четных. Найти индекс, начиная с которого все числа четные.

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

Поэтому зачастую такие задачи сформулированы таким образом: дан отсортированный массив размера $n$. Нужно ответить на $m$ запросов вида «встречается ли число $x_i$ в массиве?». Подобные задача решается за $O(n + m\log)$ — нужно сначала создать массив за $O(n)$ и $m$ раз запустить бинарный поиск.

#Бинарный поиск с вещественными аргументами

У нас все еще есть функция-предикат $f(x)$, которая сначала равна нулю, а потом единице, и мы хотим найти это место, где она меняет значение. Но теперь аргумент функции — вещественное число.

Пример такой функции:

$$ f(x) = \begin 0, & x^2 На самом деле, так можно искать ноль любой непрерывной функции (мы сейчас искали ноль функции $x^2 - 2$), у которой известны значения аргумента, при которых она принимает значения меньше нуля и больше нуля.

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

Рассмотрим задачу: дан массив a[], состоящий из целых чисел, и требуется найти в нём элемент x. Если x присутствует в a, то нужно вернуть его индекс (если x встречается несколько раз, то можно вернуть любой из подходящих индексов), иначе, если x нет, — вернуть -1.

Простейший способ решить такую задачу — пройти по всем элементам массива и сравнить их с x:

int search(int a[], int size, int x) < // ищем x в массиве a размера size for (int i = 0; i < size; i++) // перебираем все элементы массива if (a[i] == x) // если элемент равен x, return i; // возвращаем его индекс return -1; // если не встретили x, возвращаем -1 >

Такое решение называют линейным поиском. Очевидно, что количество действий, которые данный алгоритм выполняет в худшем случае (когда x отсутствует в массиве), пропорционально размеру массива (поиск выполняется за O(N)).

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

  • Найдём центральный элемент массива и сравним его с x. Если он равен x, то ответ найден;
  • Если центральный элемент меньше x, то искать ответ имеет смысл только в правой половине массива (так как слева все элементы тоже меньше x);
  • Если центральный элемент больше x, то искать ответ имеет смысл только в левой половине массива (так как справа все элементы тоже больше x);
  • При переходе в ту или иную половину мы снова определяем в ней средний элемент и сравниваем его с x, и так далее, пока ответ не будет найден или пока в рассматриваемой области не останется элементов.

Для того, чтобы отслеживать текущую область поиска, заведём индексы l и r. Будем считать, что поиск производится в отрезке от l до r включительно; таким образом, изначально l = 0, r = size - 1. Зная l и r, середину можно найти как (l + r) / 2 или l + (r - l) / 2.

int binarySearch(int a[], int size, int x) < // ищем x в отсортированном массиве a размера size int l = 0, r = size - 1; // ищем в отрезке [l; r]. изначально это весь массив while (l return -1 // если не встретили x, возвращаем -1. >

Такое решение называют бинарным поиском. Бинарный поиск гораздо быстрее линейного, так на каждой итерации он сокращает область поиска в два раза (поиск выполняется за O(logN)).

Число сравнений в худшем случае

Размер массива Линейный поиск Бинарный поиск
10 10 4
100 100 7
1000 1000 10
10 6 10 6 20
10 9 10 9 30

Для бинарного поиска массив должен быть отсортирован, в общем случае сортировка требует времени O(NlogN).

  • Если элемент ищется лишь один раз, а массив не отсортирован, то выгоднее использовать линейный поиск (O(N) выгоднее, чем O(NlogN) + O(logN));
  • Если элементы ищутся много раз, то выгоднее отсортировать массив и использовать бинарный поиск (O(NlogN) + много O(logN) выгоднее, чем много O(N));
  • Если элементы добавляются и удаляются, то вместо отсортированного массива следует использовать другую коллекцию — двоичное дерево поиска или хеш-таблицу;
  • При помощи хеш-таблицы можно решать исходную задачу эффективнее, чем двоичным поиском, — за константное время (O(1)). Но идея двоичного поиска применима в существенно более широком наборе задач, как мы увидим далее.

Левый и правый бинарный поиск

Рассмотренная выше задача, в которой требуется найти любое вхождение заданного элемента в массив, встречается сравнительно редко и представляет мало интереса. Гораздо важнее другой вид задач: дан отсортированный массив a[] и требуется найти в нём индекс первого или последнего вхождения числа x (или индекс последнего элемента, меньшего x, или индекс первого элемента, большего x).

При решении данной задачи мы уже не можем сразу вернуть индекс, как только нашли элемент, равный x, и функцию поиска придётся усложнить.

Оказывается, что написание бинарного поиска первого или последнего вхождения — достаточно трудная задача. Программист вынужден держать в голове множество тонких моментов. Вот некоторые из них:

  • Является ли диапазон от l до r отрезком или полуинтервалом, как он отсортирован, содержит ли он искомый элемент;
  • Как следует проверять центральный элемент и как смещать границы: l = m или l = m + 1, r = m или r = m - 1;
  • Будет ли поиск правильно работать на массивах из 0, 1, 2 элементов;
  • Какой из индексов в итоге указывает на ответ, как проверить, что ответ отсутствует, и др.

Правила написания бинарного поиска без головной боли

  • Диапазон от l до r — всегда отрезок (включительно, [l; r]), изначально l = 0, r = size - 1. Искомый элемент изначально может как быть в отрезке, так и не быть, это не важно;
  • Поиск всегда осуществляется до двух элементов (while (l + 1 < r));
  • После проверки среднего элемента границы всегда смещаются только на середину (l = m или r = m, никаких плюс-минус единиц);
  • Смещение границ должно происходить так, чтобы не потерять искомый элемент (чтобы он не выпал из отрезка [l; r], если он там был).
  • Когда цикл завершится, останутся два соседних элемента — a[l] и a[r]. Их нужно проверить по отдельности. При этом, если мы ищем первое вхождение чего-либо, то сначала проверяем a[l], затем a[r]; если ищем последнее вхождение — сначала a[r], затем a[l].

Следуя этим правилам, вы сможете практически единообразно писать различные виды левых и правых двоичных поисков. Сравните показанные ниже примеры: в них меняются только условие проверки среднего элемента (выделено красным) и порядок проверки последних двух элементов (выделено оранжевым).

// сорт. по неубыванию // последний элемент < x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] < x) l = m; else r = m; > if (a[r] < x)return r; if (a[l] < x)return l; return -1;
// сорт. по неубыванию // последний элемент a[m] ) l = m; else r = m; > if (a[r] return r; if (a[l] return l; return -1;
// сорт. по неубыванию // последний элемент == x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] ) l = m; else r = m; > if (a[r] == x) return r; if (a[l] == x) return l; return -1;
// сорт. по неубыванию // первый элемент > x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] ) // if (a[m] > x) l = m; // r = m; else // else r = m; // l = m; > if (a[l] > x) return l; if (a[r] > x) return r; return -1;
// сорт. по неубыванию // первый элемент >= x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] < x) // if (a[m] >= x) l = m; // r = m; else // else r = m; // l = m; > if (a[l] >= x) return l; if (a[r] >= x) return r; return -1;
// сорт. по неубыванию // первый элемент == x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] < x) // if (a[m] >= x) l = m; // r = m; else // else r = m; // l = m; > if (a[l] == x) return l; if (a[r] == x) return r; return -1;
// сорт. по невозрастанию // последний элемент > x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] > x) l = m; else r = m; > if (a[r] > x) return r; if (a[l] > x) return l; return -1;
// сорт. по невозрастанию // последний элемент >= x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] >= x) l = m; else r = m; > if (a[r] >= x) return r; if (a[l] >= x) return l; return -1;
// сорт. по невозрастанию // последний элемент == x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] >= x) l = m; else r = m; > if (a[r] == x) return r; if (a[l] == x) return l; return -1;
// сорт. по невозрастанию // первый элемент < x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] >= x) // if (a[m] < x) l = m; // r = m; else // else r = m; // l = m; > if (a[l] < x)return l; if (a[r] < x)return r; return -1;
// сорт. по невозрастанию // первый элемент a[m] > x) // if (a[m] ) l = m; // r = m; else // else r = m; // l = m; > if (a[l] return l; if (a[r] return r; return -1;
// сорт. по невозрастанию // первый элемент == x int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (a[m] > x) // if (a[m] ) l = m; // r = m; else // else r = m; // l = m; > if (a[l] == x) return l; if (a[r] == x) return r; return -1;
// f() возвращает // сначала true, потом false // последний f() == true int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (f(a[m])) l = m; else r = m; > if (f(a[r])) return r; if (f(a[l]) return l; return -1;
// f() возвращает // сначала false, потом true // первый f() == true int l = 0, r = size - 1; while (l + 1 < r) < int m = l + (r - l) / 2; if (!f(a[m])) // if (f(a[m])) l = m; // r = m; else // else r = m; // l = m; > if (f(a[l]) return l; if (f(a[r])) return r; return -1;

При желании показанный алгоритм можно оптимизировать, сократив количество проверок в конце.

Ссылки

  • Codeforces EDU — Двоичный поиск
  • neerc.ifmo.ru/wiki — Целочисленный двоичный поиск
  • neerc.ifmo.ru/wiki — Вещественный двоичный поиск
  • brestprog — Бинарный поиск
  • algorithmica.org — Бинарный поиск
  • Калинин П. — Бинарный поиск
  • Brilliant.org — Binary Search

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *