Як знайти елемент у масиві лінійним пошуком?

АлгоритмиJunior~1 хв читання

Коротка відповідь

Лінійний пошук - це послідовний обхід масиву зліва направо з порівнянням кожного елемента з шуканим значенням. Щойно елемент знайдено, повертаємо його індекс; якщо пройшли весь масив і не знайшли, повертаємо -1. Час: O(n), пам'ять: O(1).

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // ранній вихід
  }
  return -1; // не знайдено
}

console.log(linearSearch([4, 2, 7, 2], 7)); // 2
console.log(linearSearch([4, 2, 7, 2], 5)); // -1

Детальний розбір

Ідея алгоритму

Йдемо від початку масиву до кінця за індексами i = 0..n-1.
Порівнюємо arr[i] з цільовим значенням (або перевіряємо предикат).
Якщо умова виконується, повертаємо i (або сам елемент).
Якщо дійшли до кінця, елемента немає (повернемо -1/undefined за контрактом функції).

Складність

Час: O(n) у гіршому та середньому випадках; O(1) у найкращому (якщо елемент перший).
Пам'ять: O(1), лише лічильник/індекс.
Стабільність: знаходить перше входження (якщо шукати "всі", знадобиться зібрати індекси).

Приклади коду

Пошук числа (повернення індексу)

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

console.log(linearSearch([10, 20, 30], 20)); // 1
console.log(linearSearch([10, 20, 30], 25)); // -1

Пошук за предикатом (об'єкти)

Зручно, коли порівняння не просте ===, а за полем/умовою.

// Повертає індекс першого елемента, що задовольняє предикат
function linearSearchBy(arr, predicate) {
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i], i, arr)) return i;
  }
  return -1;
}

const users = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 3, name: 'Alice' }
];

const idx = linearSearchBy(users, (u) => u.name === 'Alice');
console.log(idx); // 0 (перше входження)

Знайти всі входження

function linearSearchAll(arr, predicate) {
  const indices = [];
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i], i, arr)) indices.push(i);
  }
  return indices; // [] якщо нічого не знайшлося
}

console.log(linearSearchAll([1, 2, 3, 2, 2], (x) => x === 2)); // [1, 3, 4]

Останнє входження (скан справа наліво)

function linearSearchLast(arr, target) {
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] === target) return i;
  }
  return -1;
}

console.log(linearSearchLast([1, 2, 3, 2, 2], 2)); // 4

Крайні випадки та практичні нюанси

Порожній масив: одразу повертаємо -1.
Дублікати: класичний варіант повертає перше входження. Якщо потрібне останнє, скануйте справа (приклад вище).
Порівняння ===: для посилальних типів порівнюються посилання, а не "вміст". Для об'єктів використовуйте порівняння за ключами або предикат.
NaN у JavaScript: NaN !== NaN, тому звичайне === не знайде NaN. Додайте перевірку Number.isNaN.
Регістр рядків: під час пошуку без урахування регістру нормалізуйте обидві сторони (toLowerCase() / localeCompare).

// Пошук із підтримкою NaN та нечутливістю до регістру для рядків
function linearSearchSafe(arr, target) {
  const isStr = typeof target === 'string';
  const normTarget = isStr ? target.toLowerCase() : target;

  for (let i = 0; i < arr.length; i++) {
    const val = arr[i];
    if (isStr && typeof val === 'string') {
      if (val.toLowerCase() === normTarget) return i;
    } else if (Number.isNaN(target) && Number.isNaN(val)) {
      return i; // обидва NaN
    } else if (val === target) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearchSafe(['a', 'B', 'c'], 'b')); // 1
console.log(linearSearchSafe([1, NaN, 3], NaN));      // 1

Коли застосовувати лінійний пошук

Малі масиви або одноразовий пошук на невеликих обсягах даних.
Набори даних не відсортовані, і недоцільно витрачати ресурси на сортування/індексацію.
Потокові дані, коли доступ лише послідовний.
Якщо пошук частий, а дані великі/статичні, розгляньте сортування + двійковий пошук або індекси (Map/Set).

Псевдокод

linear_search(A, x):
  for i from 0 to length(A) - 1:
    if A[i] == x:
      return i
  return -1

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.