Линейный поиск в JavaScript
В контексте компьютерных наук поиск - это процесс поиска определенного элемента в заданном списке / массиве. Если внимательно присмотреться, алгоритмы поиска можно найти везде.
Рассмотрим процесс входа на веб-сайт. Введенный адрес электронной почты и пароль ищутся по существующим парам ключ-значение в базе данных для проверки пользователя.
В этой статье давайте рассмотрим самый простой алгоритм поиска по заданному списку элементов - линейный поиск.
Что такое линейный поиск
Алгоритм линейного поиска - это набор инструкций для обхода данного списка и проверки каждого элемента в списке, пока мы не найдем тот элемент, который ищем. Технический термин для искомого элемента - ключевой.
Алгоритм переходит от самого левого (или начального) элемента и продолжает поиск, пока не найдет желаемый элемент или не пройдется по всем элементам в списке.
Если элемент найден, мы вернем позицию (или index) элемента. Если искомого элемента нет в списке, мы обычно возвращаемся -1.
Реализация линейного поиска в JavaScript
Мы можем перемещаться по заданному списку с помощью цикла for. Давайте посмотрим на реализацию линейного поиска:
function linearSearch(arr, key){
for(let i = 0; i < arr.length; i++){
if(arr[i] === key){
return i
}
}
return -1
}
Здесь мы просматриваем все элементы в массиве и сравниваем каждый элемент с ключом. Если мы находим совпадение, мы возвращаем индекс элемента. В нашем случае переменная i отслеживает, где мы находимся в массиве, и если мы находим совпадение, мы возвращаем текущее значение для i.
Если элемент не существует в нашем списке, функция linearSearch не вернет никакого значения i из цикла. Мы сразу после цикла устанавливаем return -1, чтобы показать, что функция не нашла нужный элемент.
Глобальный линейный поиск
В предыдущей реализации мы возвращаем значение после того, как встретим первое вхождение искомого элемента (key). Но что, если мы хотим получить индексы всех вхождений данного элемента?
Здесь на помощь приходит глобальный линейный поиск. Это вариант линейного поиска, в котором мы ищем несколько вхождений данного элемента.
Посмотрим на реализацию глобального линейного поиска:
function globalLinearSearch(arr, key){
let results = []
for(let i = 0; i < arr.length; i++){
if(arr[i] === key){
results.push(i)
}
}
// If results array is empty, return -1
if(!results){
return -1
}
return results
}
В этом случае вместо немедленного возврата индекса соответствующего элемента мы сохраняем его в массиве. В итоге мы возвращаем массив индексов.
Эффективность линейного поиска
Линейный поиск - классический пример алгоритма грубой силы. Это означает, что алгоритм не использует никакой логики, чтобы попытаться сделать то, что он должен делать быстро, или как-то уменьшить диапазон элементов, в которых он ищет key. Другие алгоритмы поиска стремятся сделать это более эффективно за счет какой-то предварительной обработки списка / массива, например, его сортировки.
Временная сложность линейного поиска составляет O(n), где n - количество элементов в списке, который мы ищем. Это потому, что при расчете временной сложности мы всегда учитываем наихудший случай. В случае линейного поиска (как и в случае с большинством поисковых алгоритмов) наихудший случай возникает, когда элемент не существует в списке. В этой ситуации нам нужно будет просмотреть все n элементов, чтобы определить, что этого элемента нет.
Вывод
В этой статье мы рассмотрели логику линейного поиска, а затем, используя эти знания, реализовали алгоритм на JavaScript. Мы также рассмотрели временную сложность алгоритма линейного поиска.
Это, безусловно, простой алгоритм поиска, который не использует никакой логики, чтобы попытаться отбросить определенный диапазон для поиска или с упором на скорость.
