Лінійний пошук

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

Якщо відрізок має довжину N, то знайти рішення з точністю до $\epsilon$ можна за час $N \over \epsilon$. Таким чином асимптоматична складність алгоритму - $O(n)$. У зв'язку з малою ефективністю в порівнянні з іншими алгоритмами лінійний пошук зазвичай використовують лише тоді, коли відрізок пошукової системи містить дуже мало елементів, однак лінійний пошук не вимагає додаткової пам'яті або обробки/аналізу функції, так що може працювати в потоковому режимі при безпосередньому отриманні даних з будь-якого джерела. Так само, лінійний пошук часто використовується у вигляді лінійних алгоритмів пошуку максимуму/мінімуму.

Як приклад можна розглянути пошук значення функції на множині цілих чисел, представленої в таблиці.

Приклад

Змінні $L$ та $R$ містять, відповідно, ліву та праву границю відрізка масиву, де знаходиться потрібний нам елемент. Пошук починають з першого елементу відрізка. Якщо шукають значення не одно значенням функції в даній точці, то здійснюється перехід до наступної точки. Таким чином, в результаті кожної перевірки область пошуку зменшується на один елемент.

int function LinearSearch (Array A, int L, int R, int Key);
begin
   for X = L to R do
     if A [X] = Key then
       return X
   return -1; // елемент не знайдено
end;

Посилання

• C++ Program - Linear Search (англ.)