Overview

In this tutorial, we will learn about Sequential Search Algorithm. Sequential search is the most natural search method. Sequential search is efficient for small lists. It takes a considerable amount of time and is slow for long lists.

In this method, the search begins with searching every element of the array or the list until the search element is found. The algorithm does not require sorted data elements in the array or the list.

Sequential Search Algorithm

Let’s look at the sequential search algorithm to search a list of values.

INPUT: Array of size N.
Search key value key
OUTPUT: The position of the key in the array arr

BEGIN
SET flag <- false
SET i <- 0
WHILE (i <=N) and (flag is false)
IF arr[i] = key
flag <- true
DISPLAY The index position i in the array.
ELSE
i=i + 1
END
IF flag is false
DISPLAY The key is not present in the array.
END

Analysis

In the above algorithm, the sequential search is carried out on an array of values. We can also use it on linked lists. The most important part is the comparisons made, the fewer the number of comparisons, the sooner the algorithm will terminate.

Best Case

The best case is when the required search item is the first item in the array or the list. The number of comparisons, in this case, is 1.

Worst Case

In the worst case, is when the required search item is the last item in the array or the list. We will traverse the entire array or the list of elements. In this case, the algorithm makes the maximum comparisons = N.

Average

Hence the average number of comparisons done by sequential search is (N+1)/2

In the next tutorial, we will learn a better and more efficient search algorithm called Binary search.