Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як знайти елемент у масиві лінійним пошуком?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

```js
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
```

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

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

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

## Складність

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

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

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

```js
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
```

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

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

```js
// Повертає індекс першого елемента, що задовольняє предикат
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 (перше входження)
```

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

```js
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]
```

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

```js
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).

```js
// Пошук із підтримкою 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
```

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати634 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.