LINEAR SEARCH ALGORITHM

WHAT THIS ALGORITHM IS ALL ABOUT?

Suppose you have some data stored in some of your data storing device. For simplicity, let's assume that you have 5 cups(data storing device) and there is some liquid in each cup(data) as shown below.

 Now you have a problem. You don't know which cup has which liquid exactly. You just have access to the number written on the cup[1,2,3,4,5]. I ask you to find the cup having "Mango Juice"! What will you do? Most probably you will do something similar to me,

1. You will pick up the first cup and check if there is "Mango Juice" inside, if that's true, you will tell that Cup - 1 has Mango Juice. If not, you will put the cup down and move to the next cup.
2. You will repeat the same step, till you find "Mango Juice" inside a cup.
3. When you will reach Cup - 4, you will find the asked data and then you will tell me that Cup-4 has "Mango Juice" inside.
4. Once you will find the required data you will stop and needn't check the remaining cups.

The same thing happens in case of solving a Searching Algorithm problem with the help of Linear Search. The simple analogy is considering the cups as some data holders for our computer program (Known as Data structures) and take an input of the required data key to search for that data in the data structure.

ANALOGY IN PROGRAMMING -

You may have come across the word Array. An array is one of the basic data structure used in programming that enables the program to store some data of the same type.

Suppose we have an array named as A as follows,

And I am asking you something similar to our Cup concept. Find the position of '5' in the array.

You will follow the same logic that I have written in simple language but we have to use some programming.

1. You will use a loop to iterate over the array from 0 to 6, i.e up to the maximum size of the array.
2. At each iteration, you will search if the value of array for that position (which is changing because of iteration) is the same as that of the key value,i.e. 5.
3. If that is same, just return the position and stop further iterations and you have the required result.

Code approach:-

• In C++

for(int i=0;i<max_size;i++)
{
  if(A[i]==key)
  {
    cout << i << endl;
    break;
  }
}

• In Python

for i in range(n):

  if A[i] == key:

    print(i)
    break

LET'S WRITE THE TOTAL CODE :

• Code in C++

#include<iostream>

using namespace std;


int main()

{

    int max_size,key;

    cin >> max_size;

    int A[max_size];

    for(int i=0;i<max_size;i++)    /// for taking the array input from user

    {

        cin >> A[i];

    }

    cin >> key;

    for(int i=0;i<max_size;i++)    /// main algorithm starts working here.

    {

        if(A[i]==key)

        {

            cout << i << endl;

            break;

        }

    }

    return 0;

}

Code in Python

n = int(input())  

key = int(input())

a = list(map(int,input().strip().split()))[:n]  # taking array input from the user

for i in range(n):                              # main algorithm

    if a[i]== key:

        print(i)

        break

I hope it will be helpful for beginners in the world of programming.

Thank you.