2.1 Linear Search

Consider We are given an array of numbers, say its:

56    89    96    544  2      366  3333        65    695  1       36    59

And We are to find out if some other number is part of this array or not, and if it is, then at what position.

Can you think of a program and write a program, which does exactly this?

Given an array, we simply need to find out if another given number exists in it or not.

We may do it as follows:

#include <iostream>

using namespace std;

int main(){

            int temp;

int array[12] = {56,89,96,544,2,366,3333,65,696,1,36,59};

            cout<<”Enter the Number you’d like to find in the array?”<<endl;

            cin>>temp;

            for(int i = 0;i<12;i++){

                        if(array[i]==temp){

cout<<”The Number is found at the ”<<i+1<<”th position”<<endl;

            }

}

                       

}

Makes Sense, right?

Notice the for loop right there, How many times do you think it will repeat to do something?

12, right?

Why?

Because There are 12 elements in the array.

Now, What if the number of elements in the array was not fixed and it had say ‘n’ elements.

Then the for loop would repeat doing the same thing n number of times, right?

We say that would be O(n) algorithm. Its just a conventional way of defining the efficiency of an algorithm based on the number of times, it does any particular thing.

Thus, We conclude that Linear Search is an O(n) algorithm, because it requires n operations to complete.

Exercise

Tell what would be the efficiency of the following program?

#include <iostream>

using namespace std;

int main(){

            int n,m;

            cin>>n>>m;                          //Taking as input from the user the dimensions of a 2-D array

            int array[n][m];

            int sum = 0;                       //Currently the sum of all terms is 0

            for(int i = 0;i<n;i++){

                        for(int j = 0;j<m;j++){

                                    cin>>arr[i][j];            //Taking as input the contents of the array

                                    sum = sum + arr[i][j];         //Adding the arr[i][j] number to the sum

}

}

cout<<sum<<endl;                                  //Printing the sum

}

NOTE: A 2D array is an array in which each and every element of the array is another array which in-turn creates a Table like structure, looking like the following:

Arr[0][0]	Arr[0][1]	Arr[0][2]	…	…	..	…	…	…	Arr[0][n]
Arr[1][0]	Arr[1][1]
Arr[2][0]
..
..
..
..
Arr[m][0]									Arr[m][n]