Примеры линейных алгоритмов javascript

Алгоритм линейного поиска в 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;
>
>

Важно отметить, что алгоритм линейного поиска не должен использовать отсортированный список. Также алгоритм может быть настроен для использования в различных сценариях, таких как поиск массива объектов по ключу. Если у вас есть массив данных о клиентах, который включает ключи для имени и фамилии, вы можете проверить, есть ли в массиве клиент с указанным именем. В этом случае вместо проверки того, равен ли list[index] нашему поисковому значению, вы должны проверить на равенство list[index].firstName.

В приведенном выше примере я использовал функцию linearSearch для массива из пяти элементов. В худшем случае, когда искомое значение отсутствует в списке или находится в конце списка, функция должна будет выполнить пять сравнений. Поскольку наш массив очень мал, нет необходимости оптимизировать его, используя другой алгоритм. Однако после определенного момента использование алгоритма линейного поиска более неэффективно, и тогда лучше использовать алгоритм двоичного (бинарного) поиска.

На этом все, в следующей статье мы поговорим об алгоритме бинарного поиска.

Создано 01.01.2019 13:58:37

Михаил Русаков

Копирование материалов разрешается только с указанием автора (Михаил Русаков) и индексируемой прямой ссылкой на сайт (http://myrusakov.ru)!

Добавляйтесь ко мне в друзья ВКонтакте: http://vk.com/myrusakov.
Если Вы хотите дать оценку мне и моей работе, то напишите её в моей группе: http://vk.com/rusakovmy.

Если Вы не хотите пропустить новые материалы на сайте,
то Вы можете подписаться на обновления: Подписаться на обновления

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

Порекомендуйте эту статью друзьям:

Если Вам понравился сайт, то разместите ссылку на него (у себя на сайте, на форуме, в контакте):

1. Кнопка:
   Она выглядит вот так:
2. Текстовая ссылка:
   Она выглядит вот так: Как создать свой сайт
3. BB-код ссылки для форумов (например, можете поставить её в подписи):

Комментарии ( 0 ):

Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.

Copyright © 2010-2023 Русаков Михаил Юрьевич. Все права защищены.

Источник

Алгоритм двоичного поиска в JavaScript

Alberta Williams Last updated May 10, 2022

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

Вступление

Как программист, вы хотите найти лучшее решение проблемы, чтобы ваш код был не только правильным, но и эффективным. Выбор неоптимального алгоритма может означать более длительное время завершения, повышенную сложность кода или, что еще хуже, ошибочную программу. Возможно, вы использовали алгоритм поиска, чтобы найти элементы в коллекции данных. Язык JavaScript имеет несколько методов, таких как find , для поиска элементов в массиве. Однако эти методы используют линейный поиск. Алгоритм линейного поиска начинается в начале списка и сравнивает каждый элемент со значением поиска, пока он не будет найден. Это хорошо, когда у вас есть небольшое количество элементов. Но когда вы ищите большие списки, которые содержат тысячи или миллионы элементов, вам нужен лучший способ найти элементы. Это когда вы будете использовать бинарный поиск. В этом уроке я объясню, как работает бинарный поиск и как реализовать алгоритм в JavaScript. Сначала рассмотрим алгоритм линейного поиска.

Линейный поиск

Мы начнем с объяснения того, как реализовать линейный поиск в JavaScript. Мы создадим функцию с именем linearSearch , которая принимает значение, являющееся целым числом или строкой, и массив в качестве параметров. Функция будет искать значение в каждом элементе массива и возвращать позицию значения в массиве, если оно найдено. Если значение отсутствует в массиве, оно вернет -1. Например, вызов linearSearch (1, [3, 4, 2, 1, 5]) вернет 3, а вызов linearSearch (0, [3, 4, 2, 1, 5]) вернет -1.

Вот некоторый псевдокод для нашей функции:

while found is false and index < number of elements

if list[index] is equal to search value

Реализация линейного поиска в JavaScript

Вот JavaScript-реализация алгоритма линейного поиска:

function linearSearch(value, list)  

while(!found && index  list.length)  

Важно отметить, что алгоритм линейного поиска не должен использовать отсортированный список. Также алгоритм может быть настроен для использования в различных сценариях, таких как поиск массива объектов по ключу. Если у вас есть массив данных о клиентах, который включает ключи для имени и фамилии, вы можете проверить, есть ли в массиве клиент с указанным именем. В этом случае вместо проверки того, равен ли list[index] нашему поисковому значению, вы должны проверить list[index] .first .

В приведенном выше примере я использовал функцию linearSearch для массива из 5 элементов. В худшем случае, когда искомое значение отсутствует в списке или находится в конце списка, функция должна будет выполнить 5 сравнений. Поскольку наш массив настолько мал, нет необходимости оптимизировать его, используя другой алгоритм. Однако до определенного момента использование алгоритма линейного поиска более неэффективно, и тогда лучше использовать алгоритм двоичного поиска.

Бинарный поиск

Представьте, что вы угадываете чисел. Вас попросят угадать число от 1 до 100. Если ваш номер слишком высокий или слишком низкий, вы получите подсказку. Какой будет ваша стратегия? Вы бы выбрали числа случайно? Начнете ли вы с 1, затем с 2 и так далее, пока не угадаете? Даже если у вас было неограниченное количество догадок, вы хотите сделать правильное предположение за минимальное количество попыток. Поэтому вы можете начать угадывать с 50. Если число больше, вы можете угадать с 75 раза. Если оно меньше, то это означает, что число находится в диапазоне от 50 до 75, и вы выбрали бы число, которое находится в середине. Вы будете продолжать в том же духе, пока не достигнете правильного номера. Это похоже на то, как работает бинарный поиск.

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

Сначала мы находим средний элемент. Это элемент в позиции Math.floor((first + last)/2) , где first - первый индекс, а last - последний индекс. Мы выбираем округление так, чтобы в случае, если результат является дробью, он становится целым числом. Средний элемент в этом списке равен 5. Наше поисковое значение 9 больше 5, поэтому мы ищем список:

Средний элемент этой части равен 8. Девять больше, чем 8, поэтому мы ищем список:

Средний элемент равен 9, поэтому мы можем остановить наш поиск здесь.

Вот некоторый псевдокод, который выражает вышеупомянутый алгоритм для двоичного поиска:

Set last to the last index in the list

while found is false and first is less than or equal to last

Set middle to the index halfway between first and last

if list[middle] equals the desired value

else if list[middle] is greater than the desired value

Реализация бинарного поиска в JavaScript

Теперь давайте закодируем алгоритм двоичного поиска в JavaScript!

Мы создадим функцию binarySearch , которая принимает значение и массив в качестве параметров. Он вернет индекс, где значение встречается в списке, если найдено. Если значение не найдено, возвращается -1. Это наша реализация, написанная на JavaScript:

function binarySearch(value, list)  

let first = 0; //left endpoint 

let last = list.length - 1; //right endpoint 

Источник