Прежде чем приступить к знакомству с бинарным поиском и битоническими массивами, нам нужно знать, что такое алгоритм. Что ж, это определение алгоритма прямо из Google : «процесс или набор правил, которым необходимо следовать при вычислениях или других операциях по решению проблем, особенно с помощью компьютера.”
Так что да, алгоритм — это набор правил для решения проблемы. И проблемы! мальчик, мы не отстаем от них. В повседневной жизни мы сталкиваемся с проблемами, которые требуют решения. Когда решения могут быть найдены, мы не довольствуемся каким-либо решением только потому, что оно решает проблему, с которой мы сталкиваемся, нам нужно принять во внимание время и пространство, занимаемое решением, чтобы определить, стоит ли в него инвестировать. Вот когда приходит наука о структурах данных, математических моделях, используемых для решения конкретной проблемы.
Что ж, позвольте мне избавить вас от нудной математики, стоящей за этим, и сразу перейти к плюсам бинарного поиска.
БИНАРНЫЙ ПОИСК
Предположим, у вас есть список чисел, и этот список отсортирован. Итак, вы хотите найти индекс элемента в этом списке. Что ж, в этом проблема.
Яп! как показано выше, наш список отсортирован, и наша цель - найти индекс, по которому находится число 5 из этого списка.
Чтобы решить эту проблему, мы можем использовать два подхода: первый — перебор, второй — бинарный поиск. Это лучше и включает в себя применение математической модели, чтобы значительно сократить время, необходимое для решения, учитывая большое количество входных данных. Как вы увидите, время в этом вопросе имеет решающее значение.
Использование грубой силы для решения этой проблемы подразумевало бы просмотр всего массива, начиная с нуля, пока мы не найдем 5 и не вернем его индекс. Что ж, при таком подходе в худшем случае, т. е. если бы 5 было в последней позиции массива, нам пришлось бы пройти весь массив, чтобы добраться до того, что мы ищем. Поэтому сложность в этом случае будет ¬ nс nколичеством элементов в массиве. Другими словами, O(n). Следовательно, чем больше n, тем больше времени требуется, чтобы найти то, что нам нужно.
С другой стороны, бинарный поиск оказывается эффективным с точки зрения времени.
Черт!!! Движения на картинке выше точны. Я не мог объяснить это лучше.
Фактически бинарный поиск можно объяснить следующими шагами:
- Найдите средний элемент в массиве
- Сравните этот средний элемент с элементом, который вы ищете
- Если элемент для поиска меньше среднего элемента, отбросить правую часть среднего элемента, но сохранить левую часть.
- Сделайте то же самое для результирующего массива, пока не найдете элемент для поиска, а затем верните его индекс.
Когда вы посмотрите на время, затрачиваемое этим алгоритмом, вы заметите, что время значительно сокращается, что большое O для этого алгоритма равно O (1logN).
Чтобы доказать это. Я написал два типа алгоритмов, и разница просто ошеломляющая. После запуска алгоритма грубой силы с использованием JavaScript время, необходимое для выполнения функции с количеством входных данных, равным 40 элементам; в ручном режиме, снятом на моем компьютере, было ~ 3 секунды. Однако при выполнении алгоритма бинарного поиска это заняло всего 0,4 секунды.
Вуаля, думаю теперь понятно, что алгоритм бинарного поиска почти в 10 раз быстрее и эффективнее при решении подобных задач. Кроме того, в зависимости от входных данных, с тысячами или миллионами входных данных, требуется более эффективный метод, и метод бинарного поиска как раз оказывается ответом на это.
Ниже показано, как код выглядит в JavaScript.
const binSearch = (array, k) => {
let low = 0; // the first element’s index
let hi = array.length — 1; //last element’s index
while(low <= hi) {
const mid = parseInt(low + (hi — low) / 2); // the middle of low an hi
if(k < array[mid]) hi = mid — 1; // Move the hi point
else if (k > array[mid]) low = mid + 1; //Move the low point
else return mid; // If k = mid
}
return -1;
}
Это знакомит меня со следующей проблемой, похожей на первую, а именно с поиском в bitonic массиве.
ПОИСК В БИТОННОМ МАССИВЕ
Подождите минуту! Что такое bitonicмассив? Подождите, это массив, как следует из названия, но массив является битоническим, если он состоит из возрастающей последовательности целых чисел, за которой сразу следует убывающая последовательность целых чисел. Скажем, у нас есть такой массив [1,2,5,7,6,3,0].
Наблюдая за этим массивом, мы замечаем, что вначале элементы сортируются в порядке возрастания, т.е. 1,2,5,7, но после 7 мы замечаем, что элементы начинают уменьшаться, т.е. 6,3,0. Да, это битонический массив.
Как указывалось ранее, чтобы лучше подойти к этой проблеме при поиске в массиве, мы должны использовать алгоритм бинарного поиска.
Просто для протокола: при применении подхода грубой силы к этой проблеме сложность составляет O (NlogN), но для алгоритма бинарного поиска сложность составляет O (2logN), что намного лучше, чем грубая сила.
Итак, вот шаги, которые нужно выполнить, чтобы решить проблему битонического массива с помощью алгоритма двоичного поиска:
- Разделите массив на две половины: возрастающую сторону как один массив и убывающую сторону как вторую.
- Затем примените алгоритм бинарного поиска к каждой стороне отдельно и
- Бинго, проблема решена!!!
Чтобы проиллюстрировать это, вот код
const binSearch = (array, k) => {
let low = 0; // the first element's index
let hi = array.length - 1; //last element's index
while(low <= hi) {
let mid = parseInt(low + (hi - low) / 2); // the middle of low an hi
if(k < array[mid]) hi = mid - 1; // Move the hi point
else if (k > array[mid]) low = mid + 1; //Move the low point
else return true; // If k = mid
}
return false;
}
const bitonic = (a, k) => {
let lo1 = 0;
let lo2 = a.length;
let hi = parseInt(lo2 / 2 + 1);
if (binSearch(a.slice(lo1, hi), k)) return true;
return binSearch(a.slice(hi, lo2), k);
}
И вуаля!!! Я надеюсь, что это письмо было информативным для вас. Очень скоро я напишу о других алгоритмах, таких как сортировка, и о том, как лучше всего к ним подойти, чтобы сэкономить время и ресурсы каждого.
Если вам понравилось то, что вы прочитали, не забудьте оставить аплодисменты и/или комментарий. Удачного взлома.
