Алгоритмы бинарного поиска объясняются на записях камер наблюдения

1656675490 algoritmy binarnogo poiska obyasnyayutsya na zapisyah kamer nablyudeniya

Юлия Гейст

-2FL8gLiWdCcpfOlb1tVp9P8D3MoK5NNgqgi

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

Контекст

Раньше я жил в доме, где была общая кухня для более чем 100 студентов. Как вы могли себе представить, в раковине почти всегда была не вымыта посуда. Группа в моей школе выдвинула идею установить Nest Cam, чтобы ловить виновных и вызвать их с помощью канала Nest Cam.

Чтобы проиллюстрировать свою точку зрения, допустим, что вы нашли грязную посуду в 12 вечера и не были на кухне целый день.

Подумайте, как бы вы искали человека, оставившего посуду. Вы бы просмотрели все 24 часа видеосъемки с самого начала, пока не найдете виновника?

Наверное, нет. Скорее всего, вы бы прыгали вокруг кадров, проверяя, была ли посуда в раковине, скажем, 12 часов назад — в 12 утра. Если бы они были, вы бы знали, что это произошло до 12 утра. После этого вы можете вернуться к 22:00. Если посуда не является теперь вы сузили временные рамки с 22:00 до 12:00 – другими словами, вы исключили любое время до 22:00. Вы бы продолжали этот процесс, пока не найдете виновника.

t1WQMX7wWxGGHHyXER-9NOVgc0FZPN2WMgAT
Бинарный поиск момента, когда оранжевую чашку ставят в раковину (использовано видео YouTube)

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

Знали вы это или нет, конкретный процесс, который мы только что прошли, это двоичный поиск! Двоичный поиск – это a очень специфический способ прыжков вперед и назад в кадре.

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

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

В примере камеры Nest Cam по каким параметрам сортируется видеоматериал? Что мы ищем в этом сортированном порядке?

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

Нам также нужно то, что мы ищем. В данном случае это наличие немытой посуды в общей раковине.

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

d27KVv4hAnngmMMZ1rz4GjXIgsceR5H9tHzP

При программировании бинарный поиск можно использовать во многих контекстах. Это есть чрезвычайно быстрый способ поиска элементов в отсортированной структуре.

Двоичный поиск может быть реализован итеративным или рекурсивным способом. Итеративная реализация использует a while петля. Между тем, рекурсивная реализация вызовет сама себя из собственного тела.

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

Дано массив отсортированных чисел, вернуть True если 53 является элементом.

[0, 3, 4, 5, 6, 15, 18, 22, 25, 27, 31, 33, 34, 35, 37, 42, 53, 60]

Итеративный

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

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

zO-GtUNZ6ezlXEHMhdvP4JjOxmmqBZCePp9L

Перед while начинается цикл, нижний предел – ноль, а верхний – длина массива. Верхний предел меняется, если число, которое мы ищем, находится в первой половине диапазона. Нижний предел меняется, если число, которое мы ищем, находится во второй половине диапазона.

Если while цикл завершается, то есть существует диапазон нулевой длины, возврат False.

def binarySearch(array, number):   lowerBound = 0   upperBound = len(array)
while lowerBound < upperBound:        middleIndex = int(math.floor(lowerBound + (upperBound —    lowerBound) / 2))        if array[middleIndex] == number:             return True        elif array[middleIndex] < number:             lowerBound += 1        elif array[middleIndex] > number:             upperBound = middleIndex   return False

Я хотел бы рассказать об этом уравнении:

int(math.floor(lowerBound + (upperBound — lowerBound) / 2))

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

Сейчас мы не знаем, какие индексы проверять в массиве. Итак, мы смещаем массив вверх за нижним пределом.

Затем мы делим это на два и округляем вниз для получения среднего индекса диапазона. math.floor возвращает a floatпоэтому мы также должны привести результат к an int.

рекурсивный

В рекурсивном подходе функция вызывает сама себя из собственного тела.

Верхний предел в этой функции – это длина переданного массива. Опять же, верхний предел меняется, если число, которое мы ищем, находится в первой половине массива. Нижний предел меняется, если число, которое мы ищем, находится во второй половине массива.

def binarySearch(array, number):    middleIndexOfArray = int(math.floor(len(array) / 2))    if middleIndexOfArray == 0:        return False
if array[middleIndexOfArray] == number:        return True   elif array[middleIndexOfArray] > number:        return binarySearch(array[:middleIndexOfArray], number)   elif array[middleIndexOfArray] < number:        return binarySearch(array[middleIndexOfArray:], number)

Затем функция вызывает саму себя, передавая в аргумент массиву половину длины массива, который являлся ее аргументом.

Если в массиве нулевые элементы, вернуть False.

Код доступен в моем репо Алгоритмы и структуры данных – отметьте его звездочкой, чтобы быть в курсе!

Следующие шаги

Я написал свой первый бинарный поиск для реализации алгоритма стохастической выборки. Он создает предложения на основе частоты слов в текстовом корпусе.

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

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

Отметьте звездочкой мои репозитории алгоритмов на Github и подпишитесь на меня в Twitter, если хотите следить за этим!

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

Ваш адрес email не будет опубликован.