Linear Search

Linear Search

by

Linear search is very simple and easy to implement and understand. We start from the left most element of the array and one by one compare the value to be searched with each elements of the array.

Approach for linear search

For example lets say, the array is [ a, b, x, z, y] and we are searching for x.

We start from the left most element of the array and here it is a. So in the first step we check if a == x (myarray[0] == x) and its false. So we check the next element b == x (myarray[1] == x) and that is also false.

Now the third element is x and x == x (myarray[2] == x) is true. So we found out value that we are searching (x) at the third position of the array as array start from zeroth index it value will be at myarray[2].

Now that we found what we need we will end our search there. We don’t have to search further.

Program explanation

One of the main part of this program is looping. To iterate or loop through each elements we will be using any looping statement. Here we are using for loop.

So this loop will go like this,

We are taking n as the number of element inside the array, in c++ we can find it using sizeof(array_name_here), this returns the size of the array.

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

The loop starts with the value of i = 0 and this is called only once. Then we check if i < n, that is, 0 < size of the array. If this is true, we execute the statements inside the loop else we exit the loop and continues with rest of the lines.

Now lets see what statement is inside the loop. Lets say our arrays name is myarray.

if (myarray[i] == x) { result = i; }

Here we checks if myarray[i] is equal to the element we are searching. If that is true, we assign the value of i to a new variable result and we need to initialize the variable result as -1 before the loop. Like,

int result = -1;

Now we can close the loop after this line, so the code so far will be like this.

int result = -1;
int n = sizeof(myarray);
for(int i = 0; i < n; i++) {
   if (myarray[i] == x) { 
      result = i;
  }
}

Now lets consider an array named myarray with elements [ 1, 3, 2, 7, 9] and we are searching for 3.

So here our loop will start from i = 0 and n (size of the array) is the number of elements in the array that is, 5.

Loop 1: i = 0, n = 5 and x = 3;

This is the first iteration, so i will be zero. Now 0 < 5 (i < n) so we execute the statement inside the loop. Here the if condition is, if (myarray[0] == 3) that is, if(1 == 3) and it’s false. So we continue to next by incrementing the value of i.

Loop 2: i = 1, n = 5 and x = 3

In the loop it checks if 1 < 5 (i<n) and its true so we execute the if statement. If (myarray[1] == 3) that is, if (3 == 3) and this is true. Since the condition is true we execute the statement inside the if condition. So we assign the value of i to result now result = 1. After that we break the loop since we found our answer and we no longer need to continue the loop.

Now after exiting the loop you have to check if the value of the variable result is equal to -1 or not. If its -1 the searched element is not present in the array else we could print the index of the element that is, results.

if(result == -1) {
   // Print searched element not present in the array.
}
else {
   // Print Searched element found at index: "result"
}

Now lets see the complete code with buying input from user and doing the linear search and then printing if present or not.

#include <iostream>
using namespace std;

int main(void)
{
    int myarray[] = { 2, 3, 4, 10, 40 };
    int x;
    cout << "Enter element to be searched: ";
    cin >> x;
    int result = -1;
    int n = sizeof(myarray);
    for (int i = 0; i < n; i++)
        if (myarray[i] == x) {
            result = i;
            break;
         }

	if(result == -1)
	    cout << "The element searched is not present in array";
        else
            cout << "The element searched is present at index " << result;

	return 0;
}

More Posts:

Leave a Comment