Бинарный поиск: НАЙДИТЕ ЭТУ ДИАГРАММУ!
Бинарный поиск — это алгоритм, используемый для поиска в отсортированном массиве путем многократного деления интервала поиска пополам. Проблемы, которые требуют использования бинарного поиска, являются общими вопросами на собеседовании, и, таким образом, этот алгоритм является тем, который соискатели работы в области технологий должны действительно понимать на концептуальном уровне, а также практиковать в максимально возможном количестве реальных ситуаций.
Когда я углубился в алгоритмы, бинарный поиск появился первым, и поначалу он меня немного сбил с толку. Просмотр учебника за уроком дал некоторое базовое понимание, но концепция не зацепила меня, пока я не подумал об этом, когда однажды заполнял диаграммы в картотеке клиники, где я работаю. Чтобы понять, что я имею в виду, вам нужно понять, как выглядит наша файловая комната.
Когда вы входите, есть 2 коридора. один для прошлогодних чартов и один для этого года. В каждом коридоре на каждой стороне стены есть диаграммы, расположенные в алфавитном порядке. Другими словами, каждый коридор в файловой комнате представляет собой отсортированный массив диаграмм.
Если вы когда-либо работали или управляли файловой комнатой, вы знаете негласную истину. Подать диаграммы проще, чем найти диаграммы. Что еще более важно, найти диаграммы так чертовски сложно, потому что они обычно не правильно поданы с самого начала. Графики 2018 года на стороне 2019 года. Диаграмма заполнена по имени, а не по фамилии. J в Q и всякие бычьи фекалии. Но давайте предположим, что файлообменник правильно рассортирован по соответствующему году и в точном алфавитном порядке. Другими словами… file_room.sort.
БУМ!
Идеально отсортированная файловая комната.
аааа, теперь этопрекрасные дни. График, который вы ищете, находится именно там, где вы ожидаете. Поиск занимает секунды. Это почему?
Ответ заключается в том, что наш мозг естественным образом использует бинарный поиск для их поиска. Если мне нужно найти диаграмму Джона Доу за 2018 год. Повторяю, в аду нет способа, я начинаю с передней части комнаты и просматриваю каждую диаграмму, пока не найду ее. Неа. Я собираюсь предположить, что это на стороне 2018 года. Другими словами, я сократил свой отсортированный набор данных вдвое.
Оказавшись в правой части комнаты, я делаю еще одно предположение, на какой стороне коридора я нахожусь. Сначала я поворачиваюсь налево, потому что Бейонсе сказала мне. (получить? налево, налево? нвм). Опять же, я слишком люблю свои большие пальцы, чтобы листать каждую диаграмму в поисках Джона Доу.
Смысл бинарного поиска заключается не в создании массива меньшего размера для последовательного просеивания, а в сравнении одного элемента массива с другим.
Вместо этого я смотрю на верхнюю часть левой стороны и вижу, принадлежит ли эта диаграмма Джону Доу.Говоря языком кода, я иду к диаграмме в середине отсортированного массива и смотрю, является ли эта диаграмма 1) диаграммой, которую я я ищу, 2) перед графиком, который я ищу, или 3) после графика, который я ищу.
Если эта диаграмма — Джон Доу, значит, моя работа сделана. Я достаю таблицу с полки. Если эта диаграмма идет после Джона Доу в алфавитном порядке, я поворачиваюсь к правой стороне. если эта диаграмма находится до Джона Доу, тогда, оставаясь на этой стороне, я прохожу половину стены с диаграммами и смотрю, находится ли эта диаграмма до или после Джона Доу. Говоря кодом, я создаю новый интервал поиска с диаграммами справа и делю его пополам. Я перехожу к этой диаграмме и провожу те же сравнения, пока не нахожу самого Джона.
Это бинарный поиск, ребята. и ваш мозг делает это каждый раз, когда вы входите в файловую комнату, так что пусть вас не пугает слово «двоичный». Это просто красивое слово для того, чтобы найти эту диаграмму. В следующий раз, когда вы будете на техническом собеседовании и услышите слова, напишите функцию, которая проверяет строку, чтобы увидеть, содержит ли она заданную букву, не сходите с ума, просто предположите, что строка — это файловая комната. Затем отсортируйте его и выполните двоичный поиск.
Компьютеры - пустышки по сравнению с вашим великолепным умом. Ваш мозг выполняет такие действия, как сканирование файловой комнаты в поисках различных буквенных тегов. Ниже приведено более точное представление того, как выглядит моя файловая комната (конечно, с использованием поддельных имен. HIPAA и все такое). Оставляйте свое решение предложенной проблемы в комментариях! Мне бы очень хотелось посмотреть, как вы найдете соединительные кабели и иголку в стоге сена с помощью двоичного поиска!
