What is Linear Search?

Linear Search, also known as sequential search, is a searching algorithm that finds an element in an array by checking each element sequentially until a match is found. Many beginning programmers might use this search method without thinking about it, as it can be represented by only a for loop and is very intuitive.

Assumptions

Linear Search Complexity

Best Worst Average
O(1) O(n) O(n)

Linear Search may often be seen as a "last resort" to more experienced programmers when no other searching algorithm is able to be utilized. In general, consider using linear sort when:

  • The list of elements is unordered.
  • It is not worth sorting the array first; especially if the array will not be needed to be searched again.

> Optimal sorting complexity is O(n log n), while worst case linear search is O(n).

Example

Consider an array with the elements { 5, 12, 3, 9, 1, 7, 4 }. This is an excellent candidate for using linear search as the list is unordered.

To find out if 4 is in the array, we can loop through each item, checking the values.

// Array to iterate over.
int [] array = { 5, 12, 3, 9, 1, 7, 4 };
// Searching the array with linear search.
function contains(int value) {
    // Iterate the array.
    for ( int i = 0; i < array.length; i++ ) {
        // Check the value.
        if ( array[i] == value ) {
            return true;
        }
    }
    // No value was matched, so we'll return false.
    return false;
}

Using this framework, the method can be edited to retrieve the index of the item being searched for as well as other interesting methods like finding the smallest item in the array.

> If we wanted to continue finding elements in the array, it might be worth sorting it to utilize binary search in further searches.

Further Resources