Линейный поиск (Linear Search)

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

Зачем нужно

Линейный поиск — базовый алгоритм, который работает на любых данных (отсортированных и нет). Это отправная точка для понимания более сложных алгоритмов поиска. В маленьких массивах он часто быстрее «умных» алгоритмов из-за простоты.

Где используется

  • Поиск в неотсортированных данных
  • Поиск по сложным условиям (не только равенство)
  • Маленькие массивы (< 100 элементов)
  • Array.prototype.find, indexOf, includes в JavaScript

Предпосылки

Алгоритм

1. Начать с первого элемента
2. Сравнить текущий элемент с целевым
3. Если совпадает — вернуть индекс
4. Если нет — перейти к следующему
5. Если дошли до конца — элемент не найден

Реализация в 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];
console.log(linearSearch(numbers, 7));  // 2
console.log(linearSearch(numbers, 5));  // -1

Поиск по условию (аналог Array.find)

function findBy(array, predicate) {
  for (let i = 0; i < array.length; i++) {
    if (predicate(array[i], i, array)) {
      return array[i];
    }
  }
  return undefined;
}

const users = [
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 35 },
];

const user = findBy(users, u => u.age > 28);
console.log(user); // { name: 'Alice', age: 30 }

Sentinel Search (поиск с барьером)

Оптимизация: устраняет проверку границы массива в цикле.

function sentinelSearch(array, target) {
  const n = array.length;
  if (n === 0) return -1;

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

  let i = 0;
  while (array[i] !== target) {  // не нужна проверка i < n
    i++;
  }

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

  // Проверяем: нашли реальный элемент или барьер?
  if (i < n - 1 || last === target) {
    return i;
  }
  return -1;
}

// На практике выигрыш ~10-20% за счёт одного условия вместо двух в цикле

Поиск всех вхождений

function findAllIndices(array, target) {
  const indices = ;
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      indices.push(i);
    }
  }
  return indices;
}

const data = [1, 3, 5, 3, 7, 3, 9];
console.log(findAllIndices(data, 3)); // [1, 3, 5]

Сложность

Случай Время Память
Лучший O(1) — первый элемент O(1)
Средний O(n/2) = O(n) O(1)
Худший O(n) — последний или нет O(1)

Когда линейный поиск — единственный вариант

// 1. Данные не отсортированы
const unsorted = [42, 7, 13, 99, 2];
// Бинарный поиск не работает → только линейный

// 2. Поиск по сложному условию
const found = users.find(u => u.age > 18 && u.role === 'admin');
// Нельзя использовать бинарный поиск для комбинированных условий

// 3. Поиск в связном списке
// Связный список не поддерживает доступ по индексу → только O(n)

// 4. Поиск подстроки (наивный)
function naiveSearch(text, pattern) {
  for (let i = 0; i <= text.length - pattern.length; i++) {
    if (text.substring(i, i + pattern.length) === pattern) {
      return i;
    }
  }
  return -1;
}

Встроенные методы JavaScript (все используют линейный поиск)

const arr = [10, 20, 30, 40, 50];

arr.indexOf(30);        // 2        O(n)
arr.includes(30);       // true     O(n)
arr.find(x => x > 25);  // 30      O(n)
arr.findIndex(x => x > 25); // 2   O(n)
arr.some(x => x > 25);  // true    O(n) (может выйти раньше)
arr.every(x => x > 5);  // true    O(n) (может выйти раньше)

Частые ошибки

  1. Использовать линейный поиск в отсортированном массиве. Если данные отсортированы — используйте Binary search (O(log n))
  2. Многократный линейный поиск. Если ищете часто — создайте Map/Set для O(1) lookup
  3. Забывать о -1 при неудачном поиске. Всегда обрабатывайте случай «не найдено»
// ПЛОХО: повторный линейный поиск = O(n²) суммарно
for (const item of bigArray) {
  if (anotherBigArray.includes(item)) { // O(n) на каждую итерацию!
    // ...
  }
}

// ХОРОШО: Set для O(1) проверки
const set = new Set(anotherBigArray); // O(n) один раз
for (const item of bigArray) {
  if (set.has(item)) { // O(1)
    // ...
  }
}

Практика

  1. Реализуйте linearSearch без использования встроенных методов
  2. Реализуйте findLastIndex — поиск с конца массива
  3. Сравните производительность indexOf и Set.has на массиве из 100 000 элементов

Связанные темы

Ресурсы

  • MDN — Array.prototype.find
  • Grokking Algorithms, глава 1 (Aditya Bhargava)
  • visualgo.net/en/sorting — визуализация алгоритмов