Ответ
Бинарный поиск (binary search) — это эффективный алгоритм для нахождения элемента в отсортированном массиве. Его принцип основан на стратегии "разделяй и властвуй": на каждом шаге алгоритм отбрасывает половину массива, в которой искомого элемента точно нет.
Благодаря этому его временная сложность составляет O(log n), что значительно быстрее линейного поиска (O(n)).
Алгоритм
- Определить левую (
left) и правую (right) границы поиска (изначально — весь массив). - Пока
left <= right, вычислить центральный индексmid. - Сравнить искомый элемент (
target) с элементомarr[mid]:- Если они равны, элемент найден, вернуть
mid. - Если
targetбольшеarr[mid], продолжить поиск в правой половине, сместивleftнаmid + 1. - Если
targetменьшеarr[mid], продолжить поиск в левой половине, сместивrightнаmid - 1.
- Если они равны, элемент найден, вернуть
- Если границы поиска сошлись (
left > right), элемент в массиве отсутствует.
Пример на Python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
# Вычисляем середину, избегая возможного переполнения для больших чисел
mid = left + (right - left) // 2
if arr[mid] == target:
return mid # Элемент найден
elif arr[mid] < target:
left = mid + 1 # Искать в правой половине
else:
right = mid - 1 # Искать в левой половине
return -1 # Элемент не найденКлючевые моменты
- Главное требование: Массив должен быть отсортирован.
- Эффективность: Значительно превосходит линейный поиск на больших объемах данных.
- Реализация: Может быть как итеративной (цикл
while), так и рекурсивной.
Ответ 18+ 🔞
А, бинарный поиск, ёпта! Ну это ж классика, как "Муму" у Тургенева, только без утопления собаки, блядь. Суть-то проще пареной репы, но народ постоянно в неё втыкается, как Герасим в немоту, блядь.
Смотри, представляешь: у тебя есть отсортированный массив. Это важно, сука, как закон — если он не отсортирован, то всё, пиздец, алгоритм накрывается медным тазом. И ты ищешь там какой-то элемент, target его зовут.
Так вот, зачем тупо, в лоб, как дурак, перебирать всё подряд за O(n), когда можно действовать с умом, как хитрая жопа? Берёшь весь массив — это твои начальные границы, left и right. А потом начинается магия, блядь.
Ты берёшь середину, mid. Смотришь: если твой искомый элемент равен тому, что в середине — о, ебать-копать, поздравляю, ты его нашёл! Возвращай индекс и иди пить чай.
Если нет — а вот тут самое интересное. Если твой target БОЛЬШЕ, чем элемент в середине, значит, всё, что слева от этой середины — это выкидыш, мусор, его можно на хуй послать. Искомый элемент, если он есть, то только в правой половине. Сдвигаешь левую границу left сразу за середину. И наоборот, если target МЕНЬШЕ — значит, правая половина нам не указ, сдвигаешь правую границу right.
И так ты на каждом шаге отбрасываешь ПОЛОВИНУ оставшегося массива. Половину, Карл! Это же овердохуища эффективно! С каждым шагом задача уменьшается в два раза. Отсюда и сложность O(log n) — это почти волшебство, по сравнению с тупым линейным поиском.
Вот смотри, как это в коде выглядит, тут всё честно, без подвоха:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
# Вычисляем середину, избегая возможного переполнения для больших чисел
mid = left + (right - left) // 2
if arr[mid] == target:
return mid # Элемент найден
elif arr[mid] < target:
left = mid + 1 # Искать в правой половине
else:
right = mid - 1 # Искать в левой половине
return -1 # Элемент не найденВидишь? Пока границы не схлопнулись (left <= right), мы долбим. Нашли — красота. Не нашли — возвращаем -1, типа, извини, дружок, тут такого нет, иди на хуй.
И главное помни, чувак: массив должен быть отсортирован. Это святое. Иначе будешь как тот Герасим — будешь мычать "му-му", а собака уже на дне, и ничего не найдёшь, только совесть потом загложет. В рот меня чих-пых, вот и весь алгоритм!