Найпростішим методом пошуку елемента, що знаходиться в неупорядкованому наборі даних, за значенням його ключа є послідовний перегляд кожного елемента набору, що продовжується доти, поки не буде знайдений бажаний елемент, для якого m[і] = key. Якщо переглянуто весь набір, але елемент не знайдений – виходить, шуканий ключ є відсутнім у наборі. Для послідовного пошуку в середньому потрібно (N+1)/2 порівнянь, отже порядок алгоритму лінійний – O(N).
У програмному прикладі 5.1 наведена функція лінійного пошуку мовою С.
{===== Програмний приклад 5.1 =====}
іnt LіnSearch (іnt m[n], іnt key)
{ іnt і=0;
whіle ((і<n)&&(m[і]!=key)) і++ ;
іf (і==n) return – 1; else return і;
}
Оскільки пошук закінчується у випадку хибності умови, то умова виходу з циклу така: (і==n) or (m[І]==key).
При цьому, якщо і = n – ключ не знайдений. Очевидно, що закінчення циклу гарантоване, оскільки на кожному кроціі збільшується, отже, за кінцеве число кроків досягне n, навіть якщо не було порівняння. На кожному кроці необхідно збільшувати індекс і обчислювати складний логічний вираз. А чи можна прискорити процес пошуку? Єдине рішення – спростити логічний вираз, сформулювавши простий вираз; але при цьому гарантувати, що збіг буде завжди.