linear search in data structure with Algo and Program

A linear search or sequential search is a searching method to check a desired element or data in a given Array in computer science.

In linear searching technique, each element of an Array is compared with the value for which we perform the search operation. If matches are found, it will return the array index where a value is present. In the worst-case complete array will be traversed for the match.

Linear search algorithm in data structure

We have an array A whose size is n then it can be denoted as A0…….An. E is an element for which we have to perform a search

Step 1: set i=0 and traverse an array element using a loop
Step 2: Compare the search value with an array element if i<n
Step 3: if Ai = E go to step 5
Step 4: increase i by 1 and go to step 2
Step 5: return i if search successful else terminate unsuccessfully

Pseudo code of Linear search technique

Below is a pseudo-code of Linear Search. This is not hardcoded. It can be change developer to developer. It is just a thought about how you can implement a linear search. Below is a pseudo-code by following which we can perform linear searching.

Here K is an array of the element, N is a total number of elements in the array, and X is a search value that we want to search in a given array.
LINEAR_SEARCH(K,n,X)

Step 1: [INITIALIZE SEARCH] SET I = 0

Step 2: repeat step 3 while I < n else Step 4

Step 3: [SEARCH FOR VALUE] if K[I] = X
Successful search
Return I and go to step 5
Otherwise 
I = I+1
Go to Step 2

Step 4: unsuccessful search
Return -1
Go to step 5

Step 5: Exit

Space and Time Complexity of Linear Search

• Best-case performance O(1)
• Average performance O(n)
• Worst-case performance O(n)
• Worst-case space complexity O(1) iterative

C Program to perform linear search

#include <stdio.h>
void  main()
{
    int arr[6] = {2,1,5,3,2,9};
    int i,a;
    int len = sizeof(arr)/sizeof(arr[0]);
    printf("enter a value you want to search: ");
    scanf("%d",&a);
    for(i=0;i<len;i++){
        if(arr[i]==a){
            printf("search found at index = %d",i);
            break;
        }
    }
    if(i==len){
        printf("no match found");
    }
    getch();
}

Some more explanation of linear search

• A sequential search or linear search is the simplest search technique where we start searching at the begining of the array or list. Here to find the desired value, we have to compare each element until we reach the end. If we found search value, then we will record the index where we have found value. And if we reached the end of the list and the value not found, then return -1 means the search value is not present in the list or array.
• Linear search is applied for both ordered and unordered array. But hopefully, its complexity not depends upon the order of the list in linear search because we won’t know what value we are looking for. Maybe if a list is sorted, then we can find it after traversal of all elements at the end, and if the list is unordered, then somewhere in the middle.

Efficiency of Linear search or sequential search

• Time taken and the number of comparison in this linear search determines this search technique’s efficiency. The number of comparisons depends on the position of the target search element. If the target element is found in the first position, only one comparison is made, and if the target element is found at the end of the list, then n comparison is made.
• Best case efficiency means if an element is found at a first position and it is denoted by O(1) and in the worst case if the element is present at the end of the list, which is denoted by O(n).

---

[wpusb]