Алгоритм линейного поиска в JavaScript

Взято из статьи https://infostart.ru/1c/articles/2412013/

Введение

Линейный поиск — один из самых простых и универсальных алгоритмов поиска элемента в массиве. Он последовательно проверяет каждый элемент массива до тех пор, пока не найдет искомое значение или не пройдет весь массив. Несмотря на свою простоту, этот алгоритм остается актуальным для небольших массивов и случаев, когда данные не отсортированы.

Принцип работы

Алгоритм линейного поиска работает по следующему принципу:

1. Начинаем с первого элемента массива.
2. Сравниваем текущий элемент с искомым значением.
3. Если значения совпадают, возвращаем индекс найденного элемента.
4. Если значения не совпадают, переходим к следующему элементу.
5. Повторяем шаги 2-4 до конца массива.
6. Если элемент не найден, возвращаем специальное значение (обычно -1).

Реализация на JavaScript

Рассмотрим базовую реализацию линейного поиска:

function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i; // Возвращаем индекс найденного элемента
}
}
return -1; // Элемент не найден
}

// Пример использования
const numbers = [4, 2, 7, 1, 9, 3];
const target = 7;
const result = linearSearch(numbers, target);

console.log(result); // Выведет: 2

Анализ эффективности

Временная сложность алгоритма линейного поиска:

• В худшем случае: O(n), где n — количество элементов в массиве.
• В среднем случае: O(n).
• В лучшем случае: O(1) — когда искомый элемент находится на первой позиции.

Пространственная сложность: O(1), так как алгоритм использует константное количество дополнительной памяти.

Практическое применение

Линейный поиск особенно эффективен в следующих случаях:

• Когда массив содержит небольшое количество элементов.
• Когда данные не отсортированы.
• Когда поиск выполняется однократно.
• Когда требуется найти первое вхождение элемента.

Оптимизации

Хотя линейный поиск нельзя существенно оптимизировать в общем случае, есть несколько улучшений:

1. Sentinel Method (метод стража) — это оптимизация классического линейного поиска, которая позволяет избежать проверки границ массива на каждой итерации.

Принцип работы

Метод основан на добавлении искомого значения в конец массива. Это позволяет:

• Убрать проверку выхода за границы массива
• Сделать цикл более эффективным
• Сократить количество условных проверок

Реализация:

function sentinelSearch(array, target) {
const n = array.length;

// Сохраняем последний элемент
const last = array[n - 1];

// Устанавливаем "стража"
array[n - 1] = target;

let i = 0;

// Ищем без проверки границ
while (array[i] !== target) {
i++;
}

// Восстанавливаем исходный массив
array[n - 1] = last;

// Проверяем корректность результата
if (i < n - 1 || last === target) {
return i;
}
return -1;
}

Преимущества и недостатки

Плюсы:

• Уменьшение количества операций сравнения
• Упрощение цикла
• Повышение производительности

Минусы:

• Необходимость модификации исходного массива
• Дополнительная память для сохранения последнего элемента
• Не подходит для неизменяемых массивов

2. Jump Search

Jump Search — это алгоритм поиска, который работает эффективнее линейного поиска на отсортированных массивах.

Принцип работы

Алгоритм делит массив на блоки фиксированного размера и:

1. Пропускает блоки, пока не найдет нужный диапазон
2. Выполняет линейный поиск внутри блока

Оптимальный размер блока: √n, где n — размер массива.

Реализация:

function jumpSearch(array, target) {
const n = array.length;
const step = Math.floor(Math.sqrt(n));

let prev = 0;

// Находим блок
while (array[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.floor(Math.sqrt(n));

if (prev >= n) {
return -1;
}
}

// Линейный поиск в блоке
while (array[prev] < target) {
prev++;

// Проверяем выход за границы
if (prev === Math.min(step, n)) {
return -1;
}
}

// Проверяем найденный элемент
if (array[prev] === target) {
return prev;
}
return -1;
}

Анализ эффективности

Временная сложность:

• O(√n) — в среднем и худшем случае
• O(1) — в лучшем случае

Пространственная сложность: O(1)

Сравнение методов

Практическое применение

Sentinel Method рекомендуется использовать:

• Когда массив небольшой
• При множественных поисках
• Когда допустимо временное изменение массива

Jump Search эффективен:

• На больших отсортированных массивах
• Когда важна скорость поиска
• При работе с последовательностями

Выводы:

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

• Размера массива
• Отсортированности данных
• Требований к производительности
• Возможностей модификации массива

Заключение

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

Подпишитесь на канал чтобы следить за выходом следующих статей серии.