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

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

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


1. Приклад

Змінні 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; 



2. Аналіз

Для списку із n елементів кращим випадком буде той, при якому шукане значення дорівнює першому елементу списку і потрібно тільки одне порівняння. Найгірший випадок буде тоді, коли значення у списку немає (або воно знаходиться в самому кінці списку), у разі чого необхідно n порівнянь.

Якщо шукане значення входить в список k раз і все входження рівноймовірно, то очікуване число порівнянь

\ Begin {cases} n & k = 0 \ \ [5pt] \ displaystyle \ frac {n + 1} {k + 1} & 1 \ le k \ le n. \ End {cases}

Наприклад, якщо шукане значення зустрічається в списку один раз, і всі входження рівноймовірно, то середнє число порівнянь одно \ Frac {n + 1} 2 . Однак, якщо відомо, що воно зустрічається один раз, то достатньо n - 1 порівнянь і середнє число порівнянь буде дорівнювати

\ Displaystyle \ frac {(n + 2) (n-1)} {2n}

(Для n = 2 це число дорівнює 1, що відповідає одній конструкції if-then-else).

У будь-якому випадку, обчислювальна складність алгоритму O (n).



3. Додатки

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

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


Література

  • Дональд Кнут Мистецтво програмування, том 3. Сортування і пошук = The Art of Computer Programming, vol.3. Sorting and Searching. - 2-ге вид. - М .: "Вильямс", 2007. - С. 824. - ISBN 0-201-89685-0