Skip to main content

Що таке лінійний пошук?

АлгоритмиJunior~2 хв читання
Запропонувати правку

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

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

  • Працює на невідсортованих даних.
  • Час: 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);

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

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

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

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