Вступление

В контексте компьютерных наук поиск - это процесс поиска определенного элемента в данном списке / массиве. Если внимательно присмотреться, алгоритмы поиска можно найти повсюду.

Рассмотрим процесс входа на веб-сайт. Введенный адрес электронной почты и пароль сравниваются с существующими парами ключ-значение в базе данных для проверки пользователя.

В этой статье давайте рассмотрим самый простой алгоритм поиска по заданному списку элементов - линейный поиск .

Понимание линейного поиска

Алгоритм линейного поиска - это набор инструкций для обхода данного списка и проверки каждого элемента в списке, пока мы не найдем тот элемент, который ищем. Технический термин для искомого элемента - ключевой .

Алгоритм переходит от самого левого (или начального) элемента и продолжает поиск, пока не найдет нужный элемент или не пройдется по всем элементам в списке.

Если элемент найден, мы вернем позицию (или 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. Мы также рассмотрели временную сложность алгоритма линейного поиска.

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