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

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

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

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

Контент

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

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

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

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

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

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

Лінійний пошук - це простий алгоритм пошуку елемента в масиві (або списку), який послідовно перевіряє кожен елемент з початку до кінця, поки не знайде шуканий або не перебере всі елементи.

- Працює на невідсортованих даних.
- Час: O(n), пам'ять: O(1).
- Повертає індекс знайденого елемента (або -1/false, якщо не знайдено).

## Розгорнута відповідь

### Визначення та ідея

Лінійний пошук (sequential search) послідовно порівнює цільовий елемент (target) з кожним елементом структури даних. Він не потребує попереднього сортування і підходить для довільних колекцій, зокрема для потокових або зв'язаних списків.

### Алгоритм (кроки)

1. Почати з першого елемента.
2. Порівняти поточний елемент з шуканим.
3. Якщо збігається - повернути його позицію/значення.
4. Інакше перейти до наступного елемента і повторювати до кінця.
5. Якщо елементи закінчилися - повідомити, що не знайдено.

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

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

### Коли використовувати

- Дані не відсортовані і сортування недоцільне.
- Малі масиви або виконується мало пошукових запитів.
- Дані надходять потоком (ітеративний доступ), наприклад, зв'язаний список.
- Потрібно просто перевірити наявність елемента (predicate-пошук).

### Псевдокод

```text
function linear_search(A, target):
  for i from 0 to length(A) - 1:
    if A[i] == target:
      return i
  return -1
```

### Реалізація: JavaScript

```javascript
// Повертає індекс знайденого елемента або -1
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (Object.is(arr[i], target) || arr[i] === target) { // коректно обробляє NaN
      return i;
    }
  }
  return -1;
}

// Варіант, що повертає boolean
function includesLinear(arr, target) {
  return linearSearch(arr, target) !== -1;
}

// Варіант з предикатом (гнучкіший для об'єктів)
function findIndexLinear(arr, predicate) {
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i], i, arr)) return i;
  }
  return -1;
}

function findLinear(arr, predicate) {
  const idx = findIndexLinear(arr, predicate);
  return idx === -1 ? undefined : arr[idx];
}
```

### Приклад використання

```javascript
const nums = [5, 2, 9, 1, 5, 6];
console.log(linearSearch(nums, 9));   // 2
console.log(linearSearch(nums, 7));   // -1
console.log(includesLinear(nums, 1)); // true

const users = [
  { id: 10, name: 'Ana' },
  { id: 20, name: 'Ben' },
  { id: 30, name: 'Cat' },
];

const idxBen = findIndexLinear(users, u => u.name === 'Ben');
console.log(idxBen); // 1

const user30 = findLinear(users, u => u.id === 30);
console.log(user30); // { id: 30, name: 'Cat' }
```

### Покрокова ілюстрація

Шукаємо 5 у [3, 4, 5, 2]: порівнюємо по порядку: 3 (ні), 4 (ні), 5 (так) - повертаємо індекс 2.

### Особливі випадки та нюанси

- Дублікати: зазвичай повертають перший знайдений індекс.
- Порівняння в JS: Object.is коректно працює з NaN і розрізняє +0/-0; поєднання Object.is || === покриває основні випадки.
- Ранній вихід: щойно знайдено елемент, цикл завершується (продуктивність найкращого випадку).
- Пошук за об'єктами: використовуйте предикат/компаратор, а не порівняння посилань, якщо потрібно порівняти за полем.
- Для дуже великих наборів даних і частих запитів вигідніше заздалегідь побудувати індекс (Map/Set) або відсортувати і застосовувати бінарний пошук.

### Порівняння з бінарним пошуком

- Вимога до даних: лінійний - будь-які; бінарний - лише відсортовані.
- Складність: O(n) проти O(log n) на пошук; але у бінарного є вартість сортування O(n log n) і підтримки порядку при змінах.
- Вибір: при поодиноких пошуках у невідсортованому масиві лінійний простіший і іноді швидший через малі константи.

### Тестові випадки

```javascript
console.assert(linearSearch([], 1) === -1);
console.assert(linearSearch([1], 1) === 0);
console.assert(linearSearch([2, 3, 4], 1) === -1);
console.assert(linearSearch([2, 3, 1, 4], 1) === 2);
console.assert(linearSearch([NaN], NaN) === 0);
console.assert(findIndexLinear([{a:1},{a:2}], o => o.a === 2) === 1);
```

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

Для рев’юера

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

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