Начиная с линейного поиска
Одна из первых вещей, которую вы узнаете, когда начинаете программировать (по крайней мере, на JS), - это знаменитый «цикл for» - разновидность линейного поиска, с помощью которого вы можете просматривать набор значений, чтобы найти конкретное, или протестировать его. подмножество, отвечающее определенным критериям. По большей части это работает довольно хорошо, например, когда вы разрабатываете приложения с низким трафиком или работаете с небольшими наборами данных. Но по мере роста требований к сложности и производительности вам потребуется использовать другой алгоритм, например двоичный поиск. Однако перед этим давайте сначала кратко рассмотрим типичный цикл for, представленный ниже. Если вы спешите войти в двоичный поиск, перейдите к последнему разделу, который включает простой двоичный поиск JS.
const arr = [2,4,3,5,7,6,8,5,10]
let target = 8
for(let i = 0; i < arr.length; i++){
// do something with arr[i] to find value 8 in the array
}
В приведенном выше примере мы последовательно перебираем каждый элемент в наборе данных и проверяем, можем ли мы найти целевое значение. Значение, которое мы ищем, может быть где угодно внутри массива. В этом примере мы нашли число после семи итеративных проверок, поскольку цель находится в 7-м индексе в массиве. Конечно, если бы цель (номер 8) была расположена в начале массива, мы могли бы сказать, что поиск по циклу выполнялся бы относительно быстро, поскольку он нашел бы цель только после одной или нескольких итераций.
На самом деле мы можем изобразить это математически, используя обозначение большой теты. Если бы число 8 было расположено в первом индексе нашего массива, мы бы сказали, что время выполнения нашего цикла for будет Θ (1). Однако, как видите, вместо этого он находится в конце массива. Поэтому можно с уверенностью сказать, что максимальное время, необходимое для выполнения цикла for, зависит от длины массива или в математических терминах; Θ (п). И Θ (1), и Θ (n) представляют минимальное и максимальное время выполнения, в котором может работать наш цикл for. Как вы уже можете сказать, тета-нотация не помогает нам точно сравнивать наш цикл for с другими алгоритмами, поскольку он может сильно варьироваться в этих пределах. Однако важно отметить, что верхняя граница Θ (n) может более существенно повлиять на производительность нашего цикла, если она станет значительно больше. Подумайте только, согласно ECMAScript - спецификации JavaScript - массив может иметь длину до 4,29 миллиарда элементов! (См. Раздел 6.1.7 ECMA в разделе «Типы объектов» - да, массивы являются объектами в JS, но об этом в другой раз).
Хотя theta дала некоторое представление о производительности нашего цикла for во время выполнения, чтобы правильно оценить сложность времени выполнения алгоритма с учетом наилучшего и наихудшего сценариев границ Θ, нам необходимо использовать другую нотацию. Введите обозначение с большой буквой О. С big-O время выполнения нашего цикла for равно O (n). Эта запись теперь ясно показывает, что производительность алгоритма линейного поиска особенно чувствительна к увеличению общего количества элементов в наборе данных. Теперь имейте это в виду, когда мы рассмотрим, чем отличается среда выполнения двоичного поиска.
Объяснение двоичного поиска
В отличие от линейного поиска, когда мы проверяем каждое число в массиве, двоичный поиск минимизирует количество элементов, которые мы должны перебирать, постоянно уменьшая вдвое набор данных и ища цель только в одной из двух половин. Для этого необходимо выполнить бинарный поиск. Перед поиском набор данных необходимо сначала отсортировать в порядке возрастания или убывания. На практике это означает, что если мы пытаемся найти число 8 в массиве, мы можем проверить одно число из набора данных и спросить, больше ли это число или меньше 8. Поскольку мы отсортировали числа в массиве, мы может определить, идет ли искомое число до или после числа, которое мы только что проверили.
Например, если мы только что проверили местоположение в массиве и нашли число 5, мы могли бы спокойно игнорировать все числа перед ним, поскольку мы понимаем, что не найдем 8 в этом диапазоне. Таким образом, нам не придется тратить время на поиск по всем этим числам, как это было с линейным поиском вначале. Кроме того, поскольку наш поиск является двоичным по своей природе (то есть состоит из двух частей), мы должны проверить среднее положение массива, чтобы мы могли разделить набор данных на две половины и решить, в какой из них искать следующую. Затем мы можем снова протестировать середину этой конкретной половины, пока не найдем цель или не закончатся половинки. Давайте визуализируем эти шаги с помощью псевдокода:
// STEP 1 first sort the array and establish a given target to search for // STEP 2 define the current search area and its midpoint // STEP 3 repeat the following until we either find 8 or run out of search area: a. check if the value in this point equals the target b. if it does, great we found it! c1. if the midpoint is greater than the target, halve the search area by searching to the left of the midpoint c2. if the midpoint is lower than the target, halve the search area by searching to the right of the midpoint
Теперь приступим к написанию нашего JS-кода для каждого шага.
Простой двоичный поиск в JavaScript
Шаг 1: отсортируйте массив и установите заданную цель для поиска
Имейте в виду, что для работы двоичного поиска мы должны сначала отсортировать наш массив чисел, чтобы мы могли оценить, является ли искомая цель ниже или выше, чем число, которое мы проверили в последний раз. Это поможет нам решить, в какую из двух половин области поиска смотреть дальше - мы реализуем это на шаге 3. Также важно помнить о сортировке, когда мы рассматриваем время выполнения двоичного поиска. Независимо от того, насколько хорошо BS работает изолированно, вы также должны учитывать дополнительное время выполнения для сортировки данных в первую очередь. Подробнее об этом позже, а пока мы будем использовать встроенный в JavaScript метод array.sort для подготовки данных для BS:
const arr = [12,5,7,3...]; const sortedArray = arr.sort() // [1,3,5,5,7,8,11,12,14,14,15,16,16,17,17,17,17,18,19,19,19]; let target = 18;
Шаг 2. D Уточните текущую область поиска
Как вы можете понять из псевдокода, теперь нам нужно определить некоторые переменные, чтобы отслеживать, сколько данных мы искали. Теперь мы могли бы использовать переменную для хранения, сколько чисел осталось пройти, так же, как мы это делали с линейным поиском (то есть, когда мы определили, что мы должны выполнять итерацию до i ‹arr.length).
Но помните, что весь смысл двоичного поиска заключается в том, чтобы не заглядывать в каждое место набора данных. BS должен многократно сокращать область нашего поиска вдвое, пока мы не добьемся успеха или не исчерпаем пространство для поиска. Таким образом, вместо того, чтобы отслеживать, сколько чисел мы перебрали, мы будем отслеживать только начальную и конечную точки каждой половины, которую мы ищем в любой заданной точке, и игнорировать то, что находится за ее пределами. Поскольку сначала мы начинаем со всего массива перед его разделением, конечная точка нашего поиска будет иметь значение 20 (последний индекс в нашем массиве), а начальная точка будет равна 0 (первый индекс в нашем массиве ). Кроме того, поскольку мы должны проверять только среднюю точку, нам также необходимо отслеживать это. Итак, давайте обновим наш псевдокод следующим образом:
const sortedArray = [1,3,5,5,7,8,11,12,14,14,15,16,16,17,17,17,17,18,19,19,19]; let target = 18; // start index of the array we are searching in let start = 0; // end index of the array we are searching in let end = arr.length - 1; // midpoint to check for the target let middle = Math.floor(start + end / 2);
Теперь поработаем над логикой деления вдвое.
Шаг 3. Повторяйте логику «проверки и уменьшения вдвое», пока мы не добьемся успеха или не выйдем из области поиска
const sortedArray = [1,3,5,5,7,8,11,12,14,14,15,16,16,17,17,17,17,18,19,19,19];
let target = 18;
let start = 0;
let end = arr.length - 1;
let middle = Math.floor(start + end / 2);
// a. check if the value in this point equals the target
if(arr[middle] === target){
// b. if it does, great we found it!
return true;
}
// c1. if the midpoint is greater than the target, halve the search area by searching to the left of the midpoint
else if(arr[middle] > target){
end = middle - 1
}
// c2. if the midpoint is lower than the target, halve the search area by searching to the right of the midpoint
else if(arr[middle] < target) {
start = middle + 1;
}
Нам нужно повторять эти шаги с циклом while, пока мы не найдем цель или не исчерпаем область поиска. Мы узнаем, что область поиска закончилась, когда начальная граница станет меньше или равна конечной границе область поиска (т.е. каждую половину, в которой мы ищем), не оставляя значений для поиска между ними. См. Ниже полное решение с добавленным журналом для отслеживания того, что происходит на каждой итерации.
Решение
Среда выполнения двоичного поиска
Скоро будет анализ
