Linear/Sequential Search

Definition

A linear/sequential search is used to check whether a given value is contained in an array. This type of search is used when the values in the array are unordered. If the values are in order a binary search will usually run faster.

Code

int linearSearch(int[] x, value){
    for (i = 0; i < x.length; i++) {
            if (x[i] == value) {
                return i;
            }
    }
    return -1;
}

The method returns a -1 if the value is not found in the array because an array cannot have a negative index.

Runtime

Best Case

Linear search will run the fastest when the value we are searching for is the first element in the array: O(1)

Worst Case

Linear search must traverse the entire array to determine that the value is not there: O(n)

Average Case

The average runtime of the algrithm is n / 2 : O(n)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License