Linear Search

Linear Search is the simplest and easiest searching algorithm. Linear search algorithm works by simply finding the desired element from start to end of the list. 

Linear search algorithm returns the index position of the element, if found in the list, else, returns false or invalid index position (i.e., -1).

WORKING OF LINEAR SEARCH

Suppose we want to find the element 13 in the array of 6 elements. Then, linear search algorithm will work as follows:

The linear search algorithm will work by traversing the whole array from beginning to end until it founds the element.

Example:


Element 13 is found at index position ‘5’. Hence, 5 will be returned.

ALGORITHM:


Algo Linear_search (arr, key)
{
// input – key to be searched and array from which it needed to be searched.
// output -   return the index position of the element to be searched, else return -1.
    1. i=0 .
    2. Loop(i < sizeof(arr))
    {
        1.  If(arr[i] == key)
        2. Return i.
                          }
                   3.  return -1.
}//END
 

C++ Program to Implement Linear Search is as follows:

#include<bits/stdc++.h>
using namespace std;
int linearSearch(int arr[],int size,int ele)
{
    // Traversing every element of the array
    for(int i = 0 ; i < size ; i++)
    {
        // If element is present in the array
        if(arr[i] == ele) 
        return i+1;
    }
    // If element is not present in the array
    return -1;
}
int main()
{
    int arr[] = { 46 , 59 , 11 , 67 , 13 , 97 } ;
    int size = sizeof(arr) / sizeof(arr[0]);
    int ele = 13;
    int res = linearSearch(arr,size,ele);
    if(res == -1)
    cout<<ele<<" is not present in the array";
    else
    cout<<ele<<" is present at "<<res<<" position";
}

OUTPUT:
13 is present at 5
Time Complexity:
The time Complexity of the Linear Search Algortihm is O(n).
Where ‘n’ is the number of elements in the array.

Related Posts:

  1. Program to Rotate Array Elements by ‘D’ positions.
  2. Program to find most frequent element in an array.
  3. Program to find pair in an array with given sum.
  4. Program to find first repeating element of an array.
  5. Program to merge two sorted arrays.
  6. Program to find missing number in an array.
  7. Program to sort if array is sorted.
  8. Program to print Alternate Elements of an Array.
  9. Program to swap kth element from beginning to kth element from end in an Array.
  10. Program to print all possible subarrays of the given array.
  11. Program to print kth smallest and kth largest element of an Array.
  12. Program to find equilibrium index of an Array.
  13. Program to find majority element of an Array.
  14. Program to find mean of the Array.
  15. Program to sort an Array of 0s and 1s.
  16. Program to convert lower-case alphabet to upper-case alphabet and vice-versa.
  17. Program to count total number of words in a string.
  18. Program to find smallest and largest word of the String.
  19. Program to find Most Frequent Character of the String.
  20. Program to Remove all the blank spaces from the String.

You may also like...