Description

Linear Search

linear search algorithm is a sequential search algorithm that starts at one end of a list and search through each element until the desired element is found, otherwise the search continues to the end of the list. It is the simplest algorithm for searching.

Implementing a linear search is simple

  • One by one, compare key with each element of array.
  • Return the index if key matches an element.
  • The return value will be -1 if key does not match any of the element.

Linear Search Program

#include<stdio.h>

int main(){

    int n;
    printf("Enter the size of array : ");
    scanf("%d", &n);

    int arr[n];

    printf("\nEnter the element in array : ");
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }


    // searching
    int isFound = 0;
    int key;
    printf("\nEnter the key do you want to searh the element : ");
    scanf("%d", &key);
    for(int i=0; i<n; i++){
        if(arr[i]==key){
            isFound = 1;
            break;
        }
    }

    if(isFound==1){
        printf("Element present in array ");
    }
    else{
        printf("Element is not present in array ");
    }
    return 0;
}

/*

Enter the size of array : 5

Enter the element in array : 4 9 2 8 7

Enter the key do you want to searh the element : 8
Element present in array 

*/

Recursive Linear Search in C

  • In the case of a Zero-sized array, return -1, which indicates that an element has not been found.
  • Check if the current element in the array matches the key by comparing arr[size-1] with key.
  • Return the key index if equal.
#include<stdio.h>
#include<stdbool.h>

bool linearSearchRecursive(int arr[], int size, int key){
     // if size of array is zero
    if(size == 0){
        return false;
    }else if(arr[size - 1] == key){
        // if the key is present in the last of the array
        return true;
    }else{
        return linearSearchRecursive(arr, size - 1, key);
    }
}

int main(){

    int n;
    printf("Enter the size of array : ");
    scanf("%d", &n);

    int arr[n];

    printf("\nEnter the element in array : ");
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }


    // searching
    bool isFound;
    int key;
    printf("\nEnter the key do you want to searh the element : ");
    scanf("%d", &key);

    isFound = linearSearchRecursive(arr, n, key);

    if(isFound){
        printf("Element present in array ");
    }
    else{
        printf("Element is not present in array ");
    }
    return 0;
}

/*

Enter the size of array : 5

Enter the element in array : 7 8 1 2 3

Enter the key do you want to searh the element : 3
Element present in array 

*/

Time Complexity of Linear Search

Case Time Complexity
Base Case O(1)
Average Case O(n)
Worst Case O(n)

Space Complexity of Linear Search

The Space Complexity of linear search is O(1).

Please Comment...

Comments

Login is mandatory to comment Please login

Recommended Posts

calculate the GCD | Euclids Algorithm | c and cpp programming language

The G.C.D. ( Greatest Common Divisor ) or H.C.F. ( Highest Common Factor ) of two numbers is the largest positive integer that perfectly divides the two given numbers.

Implement queue using linked list C program

In computing, queues are linear data structures that follow the First In, First Out (FIFO) principle. They are used to perform enqueuing and dequeuing operations.