Linear Search

Obaydur Rahman

Obaydur Rahman Full Stack Software Engineer

Linear Search

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

How does Linear Search work?

Linear Search

In the above example, we have a list of numbers 1 to 7 and we want to find the number 5 in it. We will start from the first element of the list which is 1. As 1 is not the number we are looking for we will check the next element which is 2. 2 is not the desired number so we will keep checking the next element until we find the number 5.

Algorithm

The algorithm for linear search is as follows:

Step 1: Set the counter variable to zero.

Step 2: Check if the target value is in counter position of the array.

Step 3: If the value is found then return the index of the value.

Step 4: Else if the value is not found then increment the counter variable by one.

Step 5: Repeat steps 2 to 4 until the counter variable is less than the length of the array.

Step 6: If the value is not found then return -1.

Pseudocode

Here is the pseudocode of the linear search algorithm.

FUNCTION linear_search(LIST[], TARGET)
    SET INDEX to 0
    REPEAT
        IF LIST[INDEX] = TARGET
            RETURN INDEX
        END IF
        INCREMENT INDEX
    UNTIL INDEX = LENGTH(LIST)

    RETURN -1
END FUNCTION

Implementation

Let's implement the above algorithm in C, Java, Python, PHP, and JavaScript.

function linearSearch(list, target) {
    for (let i = 0; i < list.length; i++) {
        if (list[i] === target) {
            return i;
        }
    }
    return -1;
}

const list = [1, 2, 3, 4, 5, 6, 7];
const target = 5;

const index = linearSearch(list, target);

if (index === -1) {
    console.log("Element not found");
} else {
    console.log("Element found at index " + index);
}

function linearSearch($list, $target) {
    for ($i = 0; $i < count($list); $i++) {
        if ($list[$i] === $target) {
            return $i;
        }
    }
    return -1;
}

$list = [1, 2, 3, 4, 5, 6, 7];
$target = 5;

$index = linearSearch($list, $target);

if ($index === -1) {
    echo "Element not found";
} else {
    echo "Element found at index " . $index;
}

def linear_search(list, target):
    for i in range(0, len(list)):
        if list[i] == target:
            return i
    return -1

list = [1, 2, 3, 4, 5, 6, 7]
target = 5

index = linear_search(list, target)

if index == -1:
    print("Element not found")
else:
    print("Element found at index", index)

public class LinearSearch {
    public static int linearSearch(int[] list, int target) {
        for (int i = 0; i < list.length; i++) {
            if (list[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] list = {1, 2, 3, 4, 5, 6, 7};
        int target = 5;

        int index = linearSearch(list, target);

        if (index == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index " + index);
        }
    }
}

#include <stdio.h>

int linearSearch(int list[], int target) {
    for (int i = 0; i < sizeof(list); i++) {
        if (list[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int list[] = {1, 2, 3, 4, 5, 6, 7};
    int target = 5;

    int index = linearSearch(list, target);

    if (index == -1) {
        printf("Element not found");
    } else {
        printf("Element found at index %d", index);
    }

    return 0;
}

Time Complexity

The worst case time complexity of linear search is O(n) where n is the number of elements in the array. The best case time complexity of linear search is O(1) when the first element is the target element.

Linear search is a very simple algorithm and it is easy to implement. But it is not very efficient when the number of elements is large. In such cases, other search algorithms like binary search are preferred.

Space Complexity

The space complexity of linear search is O(1) as it requires only a single additional memory space to store the index variable. So linear search algorithm is an in-place algorithm.

CaseTime ComplexitySpace Complexity
Worst CaseO(n)O(1)
Average CaseO(n)O(1)
Best CaseO(1)O(1)

Linear search can be used to search small to medium sized unsorted data sets. For example searching for a name in a phone book, searching for a number in a list, etc.

  • It is very simple to implement.
  • It is easy to understand.
  • It is very fast for small data sets.
  • It is very slow for large data sets.

Common Questions

Question: What is the time complexity of linear search?

Answer: The time complexity of linear search is O(n).

Question: What is the space complexity of linear search?

Answer: The space complexity of linear search is O(1).

Question: What is the difference between linear search and binary search?

Answer: Binary search is a much faster algorithm than linear search. Binary search works on sorted data sets whereas linear search works on both sorted and unsorted data sets.

Question: What is the difference between linear search and sequential search?

Answer: Linear search and sequential search are the same thing. They are both used to search for an element in a list.

Question: What is the difference between linear search and interpolation search?

Answer: Interpolation search is a much faster algorithm than linear search. Interpolation search works on sorted data sets whereas linear search works on both sorted and unsorted data sets.

Conclusion

Reading this article, you should have a good understanding of linear search algorithm. You should be able to implement linear search in your programs.

References