Узнайте, как быстро и эффективно выполнять поиск в массиве
Мы все были там раньше. Вы находитесь на техническом этапе собеседования, и интервьюер просит вас написать бинарный поиск. Если вы похожи на меня, вы можете запереться.
Позвольте мне быть откровенным, мне не нравятся собеседования по программированию. Мысль о том, что меня поставят на место, вызывает у меня сильный дискомфорт. Добавьте к этому тот факт, что кто-то наблюдает за тем, что вы делаете, все становится в десять раз хуже. Я застрял в прошлом и чувствовал, что не могу закодировать то, что хотел объяснить в своей голове.
К счастью для вас, я написал простое руководство, в котором описывается, как написать бинарный поиск с использованием 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 .