Linear Search Algorithm

Linear Search, the most basic and easiest searching algorithm that we even use in our daily life. Yes, linear search is nothing but searching one after the other till we find what we want in a sequence one by one.

Definition

Linear Search is also known as Sequential Search, is a searching algorithm where we determine whether a given element is present in a list of items by comparing one by one, till we reach the end of the list.

Explanation

Consider the below Array fo numbers, and we’re searching for 3

[4][1][3][2]

We start comparing, S=3 with each element in the list, one by one until it’s found. If it’s not found even after reaching the end of the list of the items then it’s not present in the list.

Linear Search Algorithm

LinearSearch(List, Value)
   for all items in the list
    if item == value
      return its position
 else return not found

Linear Search Program C++

#include <iostream>
using namespace std;

int LinearSearch(int array[], int s, int n)
{
    for (int i = 0; i < n; i++)
        if (array[i] == s)
            return i;
    return -1;
}

int main()
{
    int array[] = {4, 1, 3, 2, 0};
    int find = 2;
    int size = sizeof(array) / sizeof(array[0]);
    int answer = LinearSearch(array, find, size);

    if (answer == -1)
        cout <<"Not Found";
    else
        cout << find <<" found at index  "<< answer;

    return 0;
}

Output

2 found at index 3

Time Complexity: O(N)

Space Complexity: O(1)

Conclusion

Though easy to understand and simple to implement Linear Seach is recommended to be used for small lists as it is easy to do so, longer lists take more time and proven to be inefficient in such cases. This post is a part of my #30DaysChallenge to write a blog post every day on what I learn, Cheers ~ Abhiram Reddy.