Linear Search Algorithm

Problem Statement: Given an array, and an element num the task is to find if num is present in the given array or not. If present print the index of the element or print -1.

Examples:

Example 1:
Input: arr[]= 1 2 3 4 5, num = 3
Output: 2
Explanation: 3 is present in the 2nd index

Example 2:
Input: arr[]= 5 4 3 2 1, num = 5
Output: 0
Explanation: 5 is present in the 0th index

Solution:

DisclaimerDon’t jump directly to the solution, try it out yourself first.

Approach

  • We are given an array in which we need to find a given element and return its index if present and -1, if not present.
  • So, we just start from the first index and traverse the whole array up to the (n-1)th element and compare each element with the given number.
  • If at some index they both match, just return the index.
  • If we reach the end of the array and no element from the array matches with the given number, return -1.

Code:

C++ Code

#include <iostream>
using namespace std;

int LinearSearch(int arr[], int n, int element){
    
    for(int i=0;i<n;i++){
        
        if(arr[i] == element){
            
            // Return index, if the given element 
            // matches with any element of array.
            return i;
        }
    }
    
    // If the given number not found.
    return -1;
    
}
int main() {
	
	// Let size of array be 5 and element 
	// to be searched for be 7.
	int n = 5, element = 7;
	int arr[n] = {1,3,5,7,8};
	cout<<LinearSearch(arr,n,element);
	
	return 0;
}

Time Complexity: O(N) { At the worst case, the whole array would be traversed i.e N elements }.

Space Complexity: O(1) { There is no extra space being used in this approach }.

Java Code

class Tuf {
    
    static int LinearSearch(int[] arr, int n, int element){
        
        for(int i=0;i<n;i++){
        
        if(arr[i] == element){
            
            // Return index, if the given element 
            // matches with any element of array.
            return i;
        }
    }
    
    // If the given number not found.
    return -1;
            

    }
    public static void main(String[] args) {

        // Let size of array be 5 and element 
        // to be searched for be 7.
        int n = 5, element = 7;
	    int[] arr = {1,3,5,7,8};
       System.out.println(LinearSearch(arr,n,element));
    }
}

Time Complexity: O(N) { At the worst case, the whole array would be traversed i.e N elements }.

Space Complexity: O(1) { There is no extra space being used in this approach }.

Special thanks to Priyanshi Goel for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article