Sequential or Linear Searching is used to search unsorted arrays. It is a simple algorithm which can serve as a good introduction to algorithms.
Suppose we have an array haystack of size N and a needle and we have to find the position of the needle in the haystack. If the needle is not present in the haystack we have to return the length of the array.
Searching sequentially means that we start at the first index and check if haystack is equal to needle. If it is, we can just return the current index and be done with it, otherwise we repeat the process for the rest of the elements untill we find the needle. If we don't find the needle even after checking all the elements in the haystack we can return the length of the array.
Let's look at the pseudocode first.
Function FindNeedleInHaystack(needle, haystack) FOR index IN 0...LEN(haystack) - 1 IF haystack[index] === needle return index return LEN(haystack)
Think back to the discussion on Big Oh. What would the worst case complexty for this program be?
The worst case would be when the number we are looking for is not available in the array. In that case we will have to iterate over all N elements of the array before we can get the output. Therefore, the complexity of this algorithm is O(N).
Try to solve the problem in Hashjar Arena before moving on to the solution here.
It really was simple, wasn't it?
Sequential search is the best we can do if an array is unsorted, but if the array is sorted we can do much better with Binary Search algorithm (aka logarithmic search).