DEV Community

Binayak Jha
Binayak Jha

Posted on

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:

Image from bp.blogspot.com

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
Enter fullscreen mode Exit fullscreen mode

Example:

A = [2, 4, 0, 1, 9]
x = 1
n = 5
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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));  
 }  
}  
Enter fullscreen mode Exit fullscreen mode

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)))
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

Follow me in Github For More: Click Here

Oldest comments (0)