Узнайте, как быстро и эффективно выполнять поиск в массиве

Мы все были там раньше. Вы находитесь на техническом этапе собеседования, и интервьюер просит вас написать бинарный поиск. Если вы похожи на меня, вы можете запереться.

Позвольте мне быть откровенным, мне не нравятся собеседования по программированию. Мысль о том, что меня поставят на место, вызывает у меня сильный дискомфорт. Добавьте к этому тот факт, что кто-то наблюдает за тем, что вы делаете, все становится в десять раз хуже. Я застрял в прошлом и чувствовал, что не могу закодировать то, что хотел объяснить в своей голове.

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

Что такое бинарный поиск?

Во время моего пребывания в ВВС США в качестве инженера комплексной авионики у нас был метод устранения неполадок в проводах, который назывался «метод полушага». По сути, мы берем отрезок провода, подключенного к компоненту, и делим его пополам, а затем проверяем любой конец. Если неисправность отображается на одном конце, а не на другом, мы начинаем устранение неполадок на том конце, на котором обнаружена неисправность.

Бинарный поиск в программировании аналогичен тому, что вы начинаете с большого массива, а затем разбиваете его посередине. Затем вы проверяете, находится ли то, что вы хотите, в верхней или нижней половине. Если в нижней половине, вы снова разделяетесь и продолжаете тестирование, пока либо не найдете то, что хотите, либо не вернетесь.

Двоичный поиск удобен при работе с большими наборами данных, которые ранее были отсортированы, когда итерация по каждому числу требует большого объема памяти или неэффективна. Вместо использования линейного поиска, который составляет O (n), более эффективно использовать двоичный поиск, который составляет O (log n).

Зачем использовать рекурсию?

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

Это натолкнуло меня на мысль о рекурсии для написания алгоритма бинарного поиска. Несколько замечаний:

  • Все, что делается с рекурсией, можно делать итеративно
  • Рекурсивные алгоритмы могут потреблять больше памяти из-за использования стека.

Написание базового случая

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

Мы можем написать простой базовый случай, который проверяет, равно ли array.length 1 и что цель не находится в массиве. Если это произойдет, мы достигли конца нашего массива, и число не находится внутри. Мы можем безопасно вернуть false.

Метод полушага

Теперь, когда у нас есть базовый вариант, нам нужно разделить наш массив пополам, а затем запустить некоторую логику для средней точки. Для этого мы будем использовать встроенный в JavaScript метод Math.floor для округления в меньшую сторону при делении длины массива на два.

Если цель равна numbers[middle], мы возвращаем true и выходим. Но что произойдет, если это ложно?

Реализация рекурсии

Мы хотим логически проверить, больше ли наше целевое число среднего или меньше среднего. Для этого мы добавим к нашему существующему логическому дереву if/else, используя операторы больше и меньше.

Если цель больше, чем numbers[middle] , мы знаем, что нам не нужно смотреть вниз в массиве. Затем мы рекурсивно вызовем binarySearch для нового массива чисел, используя метод slice.

Как показано выше, мы можем сделать тот же рекурсивный вызов, если число target меньше numbers[middle]. На этот раз мы создадим новый массив чисел, используя метод slice и введя начало 0 и конец middle.

Собираем все вместе

Теперь, когда у нас есть базовый вариант и логика, мы можем полностью написать нашу функцию и вызвать ее с нашим массивом и целью.

Поскольку 10 находится внутри массива, result должно быть true.

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

Краткое содержание

Написание бинарного поиска с использованием рекурсии просто и эффективно. С предварительно отсортированными данными мы можем выполнять итерацию быстрее, чем метод линейного поиска. Скажем, у вас есть массив из миллиона элементов. При линейном поиске алгоритму потребуется один миллион итераций, так как линейный поиск — это O(n). При бинарном поиске алгоритм будет состоять из двадцати шагов. Гораздо эффективнее!

Джонатан Томпсон работал инженером по программному обеспечению в компании Pendo.io, пока его не уволили в июне 2023 года. В настоящее время он ищет свое следующее большое приключение в мире разработки программного обеспечения, автоматизации тестирования и инструментов контроля качества. .

В настоящее время он проживает в Роли, Северная Каролина, со своей женой и Голдендудлом по имени Уинстон. Вы можете связаться с ним в LinkedIn или подписаться на него в Twitter или Github.

Дополнительные материалы на PlainEnglish.io.

Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .