Давайте займемся двоичной системой, детка.
Мой друг недавно порекомендовал мне выучить базовый алгоритм, который изучают студенты первого курса информатики: бинарный поиск. У нас что-то вроде отношений студент-наставник (он недавний выпускник CS из Нью-Йоркского университета), а я студент веб-разработчика/программист-любитель. Мы много играем вместе в видеоигры (ура, Overwatch!). Я изучаю веб-дизайн в школе Flatiron уже почти год, но на самом деле я не посвящал свое время углубленному изучению тем компьютерных наук.
Но что меня поразило, так это то, что он заявил следующее:
"Братан. Вы даже не знаете, нравится ли вам программирование, пока не изучите бинарный поиск».
Хорошо. Вызов принят. Я подумал: эй, я написал несколько приложений раньше, я кодирую уже около года — насколько это может быть сложно?
И вот что интересно: Это не так.
Так что же такое бинарный поиск?
По сути, это метод «разделяй и властвуй», который используется для поиска в массиве данных, многократного деления массива на половину его размера, пока не будет найден правильный элемент.
Условие состоит в том, что массив должен быть отсортирован, прежде чем бинарный поиск сможет сработать. Давайте взглянем:
Представьте, что у нас есть такой массив:
var array = [7, 2, 3, 9, 4, 13, 26, 8, 10];
Если бы я попросил вас найти индекс элемента 4, как бы вы искали этот элемент в массиве?
Естественно, вы бы использовали подход, основанный на сравнении, что-то вроде: «Ну, я просто пройдусь по массиву и сравню каждое число с 4 — если числа не совпадают, отбросьте каждый неверный результат и двигайтесь дальше». , обходя длину массива и просматривая каждый элемент, пока не найдем число 4, тогда у нас будет его индекс. Вы наверняка уже это делали, пока читали эту статью: элемент 4 лежит в 4-м индексе массива. Такой подход называется линейным поиском. Проходим весь набор данных и сравниваем каждый элемент набора данных с параметром поиска. Вы делаете это регулярно в своей повседневной жизни. Потеряли ключи от своего дома? Пройдите через каждое укрытие и область вашего дома, пока не найдете его, начните с кухни, затем гостиной, ванной и устраните каждое условие, пока не найдете свои ключи, которые все это время лежали в вашей спальне. время. Достаточно легко.
Но что, если я дам вам массив из миллиарда элементов? Или хотя бы тысячу элементов? И я прошу вас найти конкретный элемент в этом наборе данных? Как бы вы поступили тогда? Вот где проявляется мощь бинарного поиска, при условии, что у вас есть отсортированный массив.
var array = [3, 4, 7, 8, 9, 10, 13, 26] // We now have a sorted array in ascending order.
Итак, как же мы можем использовать магию бинарного поиска в этом массиве?
Ключевым компонентом бинарного поиска является вычисление среднего значения массива путем сложения его минимального и максимального значений и деления на 2 (это медиана набора данных). С этим средним значением мы сравним его с нашим целевым значением (числом, которое мы ищем), и это даст нам 3 ключевых элемента информации:
- Среднее значение равно целевому значению. Хороший! Мы нашли свою стихию! Мы можем остановиться сейчас.
- Среднее значение больше целевого значения.
- Среднее значение меньше целевого значения.
Итак, в обычном случае, когда нам не везет и мы находим свой элемент с первой попытки, мы приходим ко второму и третьему сценариям. Что мы можем сделать с этой информацией? И как мы можем логически двигаться вперед с новой информацией, полученной в результате наших усилий?
Помните, я говорил, что необходимым условием бинарного поиска является его отсортированность?
Если среднее значение больше целевого, то мы можем обоснованно предположить, что все элементы, лежащие слева от индекса среднего значения в массиве, не могут содержать искомое целевое значение. Это связано с тем, что массив отсортирован, каждый элемент находится в порядке возрастания, поэтому имеет смысл, что все элементы, лежащие слева (или меньше целевого значения), должны быть неверными.
Точно так же, если среднее значение меньше целевого значения, то можно с уверенностью сказать, что все элементы, лежащие справа (или больше целевого значения) индекса среднего значения, не могут содержать целевое значение. мы ищем.
Вооружившись этой информацией, мы теперь можем понять, что можем вырезать половину нашего массива. И мы можем продолжать использовать эту технику, чтобы многократно делить массив пополам, пока не найдем целевое значение.
Вот бинарный поиск, написанный на Javascript:
Пара ключевых моментов, на которые стоит обратить внимание:
- В строке 9 мы используем Math.floor, потому что нам не нужны десятичные числа/числа с плавающей запятой, только целые числа.
- Строки 16 и 17 самые важные и трудные для понимания. Здесь мы сдвигаем минимальное и максимальное значения вправо и влево соответственно в зависимости от того, что возвращает среднее значение. Если он возвращает меньше чем, то мы сдвигаем нашу начальную точку на единицу вправо, что сокращает массив вдвое, отбрасывая все элементы, которые меньше целевого значения. То же самое для большего, чем.
- В строке 24 мы возвращаем -1, если массив не содержит нашего целевого значения.
Выводы. Сверху вниз.
Анализ эффективности бинарного поиска дает довольно интересные результаты:
В лучшем случае бинарный поиск возвращает временную сложность O(1) времени. В худшем случае он возвращает O(log n) раз, где n — это количество элементов в массиве, а log n оценивает шаги, необходимые для нахождения целевого значения и возврата положительного или нулевого значения. результат. Это намного лучше, чем линейный поиск, чей наихудший сценарий выполняется за время O(n), когда нам нужно просмотреть каждый элемент в наборе данных.
Если вам нужны дополнительные пояснения или помощь по бинарному поиску, посмотрите видео ниже от CS50:
