Алгоритм линейного поиска в JavaScript
При создании приложения часто необходимо найти оптимальное, с точки зрения производительности, решение, которое будет выполняться достаточно быстро, и потреблять как можно меньше памяти. Поэтому, в данной и следующей статье я расскажу вам об алгоритмах линейного и бинарного поиска.
Вступление
Программист часто хочет найти лучшее решение проблемы, чтобы код был не только правильным, но и эффективным. Выбор неоптимального алгоритма может привести к медленному исполнению программы, повышенной сложности кода или, что еще хуже, к ее нестабильной работе.
Скорее всего, вы уже использовали алгоритм поиска, чтобы найти элементы в коллекции данных. Язык JavaScript имеет несколько методов, один из которых метод find, предназначен для поиска элементов в массиве. Однако эти методы используют алгоритм линейный поиск. Алгоритм линейного поиска начинает поиск с начала списка и сравнивает каждый элемент коллекции со значением поиска, пока он не будет найден.
Поиск работает достаточно быстро, когда у вас есть небольшое количество элементов. Но когда вы ищете в больших списках, которые содержат тысячи элементов, вам понадобиться более эффективный способ найти необходимое значение. В этом случае лучше использовать бинарный поиск, о котором я расскажу в следующей статье. А сейчас мы рассмотрим алгоритм линейного поиска.
Линейный поиск
Начнем с того, как реализовать линейный поиск в JavaScript. Для этого создадим функцию с именем linearSearch, которая принимает значение, являющееся целым числом или строкой – это значение мы будем проверять на присутствие в массиве, и массив, в котором будет непосредственно производиться поиск. Функция будет искать значение, сравнивая его с каждым элементом массива и возвращать соответствующую позицию значения в массиве, если оно найдено. Если значение отсутствует в массиве, оно вернет -1. Например, вызов linearSearch (1, [3, 4, 2, 1, 5]) вернет 3, а вызов linearSearch (0, [3, 4, 2, 1, 5]) вернет -1.
Вот JavaScript реализация алгоритма линейного поиска:
/**
* value - значение, которое мы ищем в массиве
* list - список значений, в которых осуществляется поиск
*
*/
function linearSearch(value, list)
{
let found = false; // флаг, сигнализирующий о том, что значение найдено
let position = -1; // позиция, в которой значение найдено, или -1, если нет такого значения
let index = 0;
// пока значение не найдено или индекс меньше длины массива
while(!found && index < list.length)
{
// если значение найдено
if(list[index] == value) {
found = true; // флаг = истина
position = index; // позиция равна индексу элемента в массиве
} else {
index += 1;
}
}
return position;
}
Важно отметить, что алгоритм линейного поиска не должен использовать отсортированный список. Также алгоритм может быть настроен для использования в различных сценариях, таких как поиск массива объектов по ключу. Если у вас есть массив данных о клиентах, который включает ключи для имени и фамилии, вы можете проверить, есть ли в массиве клиент с указанным именем. В этом случае вместо проверки того, равен ли list[index] нашему поисковому значению, вы должны проверить на равенство list[index].firstName.
В приведенном выше примере я использовал функцию linearSearch для массива из пяти элементов. В худшем случае, когда искомое значение отсутствует в списке или находится в конце списка, функция должна будет выполнить пять сравнений. Поскольку наш массив очень мал, нет необходимости оптимизировать его, используя другой алгоритм. Однако после определенного момента использование алгоритма линейного поиска более неэффективно, и тогда лучше использовать алгоритм двоичного (бинарного) поиска.
На этом все, в следующей статье мы поговорим об алгоритме бинарного поиска.
-
Создано 01.01.2019 13:58:37
-
Михаил Русаков
Комментарии (0):
Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.