Linear Search: A Guide To DSA (2)

If you want to learn about Big O : Click Here

Linear Search:

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

Time Complexity: O(n) where n is the number of elements in the array, because the worst case scenario is that the element is not present in the array and we have to traverse the whole array.

Image of Linear Search Searching an Array:

Algorithm:

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

Example:

A = [2, 4, 0, 1, 9]
x = 1
n = 5

Solving the above example:

Step 1: i = 1
Step 2: 1 <= 5
Step 3: A[1] = 4 != 1
Step 4: i = 2
Step 5: 2 <= 5
Step 3: A[2] = 0 != 1
Step 4: i = 3
Step 5: 3 <= 5
Step 3: A[3] = 1 = 1
Step 6: Print Element 1 Found at index 3

Pseudocode:

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure

Implementation:

C:

#include <stdio.h>
// Search an element in an array using linear search
void search(int arr[], int n, int x){
    int i;
    for(i=0; i<n; i++){
        if(arr[i] == x){
            printf("Element found at index %d", i+1);
            return;
        }
    }
    printf("Element not found");
}
// Main function
int main(){

    int arr[] = {10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 35;
    search(arr, n, x);
    return 0;
}

Java:

public class LinearSearchExample
{  
 public static int linearSearch(int[] arr, int key)
 {  
  for(int i=0;i<arr.length;i++)
  {  
   if(arr[i] == key)
   {  
     return i;  
   }  
  }  
  return -1;  
 }

 public static void main(String a[])
 {  
  int[] a1= {10,20,30,50,70,90};  
  int key = 50;  
  System.out.println(key+" is found at index: "+linearSearch(a1, key));  
 }  
}

Python:

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

arr = [2, 0, 1, 9]
x = 1

print("Element found at index " + str(linear_search(arr, x)))

C++:

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}

int main(void)
{
    int arr[] = { 2, 0, 1, 9 };
    int x = 1;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = linearSearch(arr, n, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}

Follow me in Github For More: Click Here

Blog