EssentialsSearch algorithms

Linear search

19 seconds read

The linear search algorithm

Linear search (or sequential search) is a simple algorithm for searching a target value in arrays and lists. The algorithm checks each element of the array until it finds an element that matches the target value. If the algorithm reaches the end of the array, it terminates unsuccessfully.

In the worst cases, it performs exactly N comparisons where N is the length of the input sequence of elements. The time complexity is O(N).

How does it work by example

Suppose, we have an array with six elements:

Our goal is to search for the index of an element that equals 20. We will start from the first element with the index 0 and compare each element of the array with the target value until we find the appropriate element.

As you may see, the linear search is absolutely simple, but it has an important feature - it can work for unsorted arrays.

Possible modifications of the linear search

Even such a simple algorithm has various small modifications:

  • checking the array contains a specified element, the result is true or false;
  • searching the first/the last occurrences of an element in the array;
  • counting all occurrences of an element in the array;
  • searching all occurrences of an element in the array;
  • searching a value only in a range of indexes of the array.
Also, the linear search algorithm can be used as a subroutine in more complex algorithms. For example, counting all occurrences elements of an array in another array.

If we know that our array is sorted (e.g. in ascending order), we could modify the linear search algorithm. If the next checked element is greater than the target value it means we will not find the value in the rest of the array and we should stop. In the next lessons, we will consider how to search in sorted arrays more effective.

If you would like to see a visualization, then input a target value and click Linear Search here.
How did you like the theory?
Report a typo