Sequential or Linear Search in an Array

Photo by Cristofer Jeschke on Unsplash

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[0] 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.

Find the needle in the haystack


Now let's look at how to implement this in code. Scroll down to find your favorite language. We cover Python, Javascript, Typescript and Golang.

Python

def find_needle_in_haystack(needle, haystack):
  for i in range(len(haystack)):
    if haystack[i] === needle
      return i
  return len(haystack)

print(find_needle_in_haystack(1, [1, 2, 3]));
Sequential search in Python

Javascript

function findNeedleInHaystack(needle, haystack) {
  for(let i = 0; i < haystack.length; i++) {
    if(haystack[i] === needle) {
      return i;
    }
  }
  return haystack.length;
}

console.log(findNeedleInHaystack(1, [1, 2, 3]));
Sequential search in Javascript

Typescript

function findNeedleInHaystack<T>(needle: T, haystack: T[]): number {
  for(let i = 0; i < haystack.length; i++) {
    if(haystack[i] === needle) {
      return i;
    }
  }
  return haystack.length;
}

console.log(findNeedleInHaystack<number>(1, [1, 2, 3]));
Sequential search in Typescript

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).

HashJar

HashJar