Проблема лінійного пошуку (також послідовний пошук, англ. linear search, sequential search) — базова задача інформатики, що полягає у знаходженні заданого елемента (ключа) в структурі даних шляхом послідовної перевірки кожного елемента до знаходження шуканого або до вичерпання всіх елементів . Це один з найпростіших алгоритмів пошуку, який не вимагає попереднього сортування даних.
Визначення та постановка задачі
Формальна постановка Дано: масив (список) елементів A = [a₁, a₂, ..., aₙ] і ключ пошуку k.
Знайти: індекс i такий, що aᵢ = k, або повідомити про відсутність елемента, якщо такого індексу не існує.
Варіанти задачі ВаріантОписРезультатПошук першого входженняЗнайти перший елемент, що дорівнює ключуІндекс першого входження або -1Пошук останнього входженняЗнайти останній елемент, що дорівнює ключуІндекс останнього входження або -1Пошук усіх входженьЗнайти всі позиції елементаСписок індексів або порожній списокПошук з предикатомЗнайти елемент, що задовольняє умовуІндекс або -1
Алгоритм
Опис алгоритму Algorithm LinearSearch(A, n, key) Input: Масив A з n елементів, ключ пошуку key Output: Індекс знайденого елемента або -1
1. for i ← 0 to n-1 do 2. if A[i] = key then 3. return i 4. end if 5. end for 6. return -1
Реалізації різними мовами Мова програмуванняКодPythonpython<br>def linear_search(arr, key):<br> for i in range(len(arr)):<br> if arr[i] == key:<br> return i<br> return -1<br>C++cpp<br>int linearSearch(int arr[], int n, int key) {<br> for (int i = 0; i < n; i++) {<br> if (arr[i] == key)<br> return i;<br> }<br> return -1;<br>}<br>Javajava<br>public static int linearSearch(int[] arr, int key) {<br> for (int i = 0; i < arr.length; i++) {<br> if (arr[i] == key)<br> return i;<br> }<br> return -1;<br>}<br>JavaScriptjavascript<br>function linearSearch(arr, key) {<br> for (let i = 0; i < arr.length; i++) {<br> if (arr[i] === key)<br> return i;<br> }<br> return -1;<br>}<br>
Аналіз складності
Часова складність ВипадокКількість порівняньСкладністьОписНайкращий1O(1)Елемент знаходиться на першій позиції НайгіршийnO(n)Елемент відсутній або знаходиться в кінці Середній(n+1)/2O(n)Елемент знаходиться в середині масиву
Просторова складність ХарактеристикаЗначенняПоясненняДодаткова пам'ятьO(1)Використовується лише змінна для індексу In-placeТакНе потребує додаткових структур даних
Математичний аналіз Середня кількість порівнянь при рівноймовірному розподілі позицій: T_avg = (1 + 2 + 3 + ... + n) / n = n(n+1) / 2n = (n+1) / 2 Імовірнісний аналіз:
Якщо ймовірність знаходження елемента на позиції i дорівнює pᵢ, то середня кількість порівнянь: Σ(i × pᵢ) Для рівномірного розподілу: pᵢ = 1/n для всіх i
Порівняння з іншими алгоритмами пошуку АлгоритмЧасова складністьВимоги до данихПросторова складністьКоли використовуватиЛінійний пошукO(n)НемаєO(1)Малі масиви, несортовані дані Бінарний пошукO(log n)Сортований масивO(1) ітеративний O(log n) рекурсивнийВеликі сортовані масиви Пошук стрибкамиO(√n)Сортований масивO(1)Великі сортовані масиви Інтерполяційний пошукO(log log n) середній O(n) найгіршийРівномірно розподілені сортовані даніO(1)Числові дані з рівномірним розподілом Хеш-таблицяO(1) середній O(n) найгіршийДодаткова структураO(n)Часті операції пошуку
Переваги та недоліки
Переваги ПеревагаОписПростота реалізаціїОдин з найпростіших алгоритмів, легко зрозуміти та реалізувати УніверсальністьПрацює з будь-якими даними (сортованими/несортованими) Мінімальні вимогиНе потребує додаткової пам'яті чи попередньої обробки Ефективність для малих масивівДля n < 10-20 може бути швидшим за складніші алгоритми через низькі накладні витрати Працює зі спискамиМожна застосовувати до зв'язаних списків, де бінарний пошук неефективний
Недоліки НедолікОписЛінійна складністьНеефективний для великих обсягів даних ПовільністьДля масивів з мільйонами елементів може бути неприйнятно повільним Не використовує структуруНе враховує можливе сортування чи інші властивості даних
Оптимізації та варіації
Sentinel Linear Search (Пошук з вартовим) Оптимізація, що усуває перевірку виходу за межі масиву на кожній ітерації: АспектСтандартний підхідЗ вартовимІдеяПеревіряти межі на кожній ітераціїДодати ключ в кінець масиву Порівнянь на ітерацію2 (межі + рівність)1 (тільки рівність)Покращення -~50% менше операцій python def sentinel_linear_search(arr, key): n = len(arr) last = arr[n-1] arr[n-1] = key
i = 0 while arr[i] != key: i += 1
arr[n-1] = last
if i < n-1 or arr[n-1] == key: return i return -1
Ordered Linear Search Для відсортованих масивів можна зупинитися раніше: ХарактеристикаЗначенняНайкращий випадокO(1) - елемент на початкуНайгірший випадокO(n) - елемент відсутній, але менший за всіСередній випадокO(n/2) - краще ніж звичайний лінійний пошук python def ordered_linear_search(arr, key): for i in range(len(arr)): if arr[i] == key: return i if arr[i] > key: # Зупинка, якщо перевищили return -1 return -1
Self-Organizing Search Метод покращення продуктивності при повторних пошуках: МетодСтратегіяЕфективністьMove-to-FrontПереміщати знайдений елемент на початок Оптимальний для часто використовуваних елементівTransposeМіняти місцями із попереднім елементом Поступове покращення для популярних елементівCountСортувати за частотою доступу Стабільно для стаціонарного розподілу запитів
Застосування
Практичні сценарії використання СценарійЧому лінійний пошукАльтернативиМалі масиви (n < 100)Простота переважає складність -Несортовані даніСортування дорожче за O(n) пошук Хеш-таблиці для багатьох пошуківЗв'язані спискиНеможливий прямий доступ Skip lists для великих списківОднократний пошукНемає сенсу оптимізувати -Потокові даніДані надходять послідовно Bloom filters для перевірки наявностіПошук за предикатомСкладна умова пошуку Індексовані бази даних
Реальні приклади ГалузьЗастосуванняОпераційні системиПошук процесу в списку активних процесівБази данихScan операція для таблиць без індексів КомпіляториПошук змінних у таблиці символів (малі таблиці) Веб-розробкаПошук елементів у DOM деревіБіоінформатикаПошук підрядка в послідовності ДНК (з модифікаціями)
Навчальне значення
Використання в освіті АспектЗначення для навчанняПерший алгоритмЧасто вивчається як перший алгоритм пошуку Основа для порівнянняБазовий рівень для оцінки інших алгоритмів Аналіз складностіПростий приклад для вивчення Big-O нотації Інваріанти циклівІдеальний для демонстрації коректності алгоритмів
Історичний контекст Лінійний пошук є одним з найдавніших алгоритмів, що використовувався ще до появи комп'ютерів при ручному пошуку в записах та картотеках. З розвитком комп'ютерних наук алгоритм став класичним прикладом для навчання та порівняння ефективності алгоритмів.
Математичні аспекти
Аналіз середнього випадку При ймовірності p знаходження елемента в масиві: C(n) = p × (n+1)/2 + (1-p) × n де C(n) - середня кількість порівнянь.
Нижня межа Для задачі пошуку в несортованому масиві лінійний пошук є оптимальним у найгіршому випадку - необхідно перевірити всі елементи, що дає нижню межу Ω(n).
Див. також
Бінарний пошук Алгоритми пошуку Аналіз алгоритмів Складність алгоритмів Структури даних
Примітки