<MyRusakov.ru />

Программирование на Python с Нуля до Гуру

Программирование на Python с Нуля до Гуру

Данный курс научит Вас программировать на языке Python, который крайне желательно знать любому, кто хоть иногда имеет дело с компьютерами. Курс состоит из 6 разделов, в которых Вы с нуля освоите этот язык и сможете создавать самые разные программы для самых разных задач любой сложности.

К курсу прилагается множество упражнений и все исходники из уроков.

Наконец, Вы получите ещё несколько бонусов: "Создание калькулятора на Python", "Создание игры на Python" и "Правильная работа со справочником".

Подробнее
Подписка

Подписавшись по E-mail, Вы будете получать уведомления о новых статьях.

Подписка Подписаться

Добавляйтесь ко мне в друзья ВКонтакте! Отзывы о сайте и обо мне оставляйте в моей группе.

Мой аккаунт Мой аккаунт Моя группа
Опрос

Каким движком Вы предпочитаете пользоваться?

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

    return position;
}

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

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

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

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

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

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

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

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

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

  1. Кнопка:

    Она выглядит вот так: Как создать свой сайт

  2. Текстовая ссылка:

    Она выглядит вот так: Как создать свой сайт

  3. BB-код ссылки для форумов (например, можете поставить её в подписи):

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

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