Linear Search

Linear Search is the most basic searching algorithm. It is also known as Sequential Search. Linear Search is a brute force algorithm. It sequentially compares each element of the array/list to the element we want to search until a match is found or the whole list has been searched.

It doesn’t depend on the arrangement of elements in an array, In simple words, the array need not be sorted.

We traverse each element of the array using a loop and compare it with the search value. See the following illustration for better understanding.

Steps Algorithm

1. Let arr[] be the array we wish to search.
2. Let N be the length of array arr[].
3. Let X be the value we want to search in arr[].
4. Traverse each element of arr[] using a loop. Perform the following steps for each element of arr[].
   1. Compare the current element of arr[] to X.
   2. If the current element is equal to X then we have found X. Print the appropriate message and exit the program.
   3. If the current element is not equal to X then move to the next element.
5. Reaching this step means that X is not equal to any element in arr[].
6. Print the appropriate message and exit the program.

Pseudo Code

arr: Array to search
n: Length of arr
x: value to search
 
FUNCTION LINEAR_SEARCH ( arr, n, x )
 
       FOR i = 0 TO n-1 DO
              IF arr[i] == x THEN
                      PRINT x is present in the array at Index i
                      RETURN
               END IF
       END FOR
 
       PRINT x is not present in the array
       RETURN
 
END FUNCTION

Program

 #include<stdio.h>
  
 // linear search function
 // arr[] is the array we want to search
 // n is the size of arr[]
 // x is the search value
 int linear_search(int arr[], int n, int x) 
 {
  
    int i;

    for (i = 0; i < n; ++i) 
	{
       if (arr[i] == x) 
	   {
        	return i;
       }
    }

    return -1;
  
 }
  
 int main()
 {
    int x, n, idx;
    int arr[] = { 5,8,1,2,13,7,9,10,11,6 };

    // length of array
    n = sizeof(arr) / sizeof(int);

    printf("\n\n   Enter value you want to search: ");
    scanf("%d", &x);

    idx = linear_search(arr, n, x);

    if (idx == -1) 
	{
        printf("   %d is not found in the array \n", x);
    }
    else 
	{
        printf("   %d is present in the array at index %d \n", x, idx);
    }
  
 } 

Output

Time Complexity of Linear Search

Best Case: O(1)
When the value we want to search is the first element of the array.

Worst Case: O(N)
When the value we want to search is not present in the array.

Average Case: O(N)
On average, we can assume that the data is present in the middle of the array. Therefore, the time complexity is O(N/2), but constants are ignored. Thus, the time complexity is O(N).

Space Complexity of Linear Search is O(1).

Linear Search Using Recursion (Recursively)

Linear search algorithm can also be implemented using recursion. This method is not widely used. This is because the space complexity of recursive implementation is O(N) and it is comparatively more complex than iterative approach.

Each recursive call compares the ith element of the array with the search value. If the search value is found, we simply return i. If the search value is not found, we increment i and call the recursive function.

Steps

1. If i == N Return -1.
2. If arr[i] == X then
   • Return i.
3. Else
   • Return linear_searchR(arr,N,i+1,X).

Pseudo Code

arr: Array to search
N: Length of arr
X: value to search

FUNCTION linear_searchR ( arr, N, i , X )

       IF i == N THEN
              RETURN -1
       ELSE IF arr[i] == X THEN
              RETURN i
       ELSE
              RETURN linear_searchR( arr, N, i+1, X)
       END IF

END FUNCTION

Program

#include<stdio.h>

int linear_searchR(int arr[], int n, int i, int x) {
        
	// i==n implies we have checked all elements of the array
	if (i == n) {
		return -1;
	}
	else if (arr[i] == x) {
		return x;
	}
	else {
		return linear_searchR(arr, n, i + 1, x);
	}

}

int main()
{
	int x, n, idx;
	int arr[] = { 5,8,1,2,13,7,9,10,11,6 };

	// length of array
	n = sizeof(arr) / sizeof(int);

	printf("\n\n   Enter value you want to search: ");
	scanf("%d", &x);

	idx = linear_searchR(arr, n, 0, x);

	if (idx == -1) {
		printf("   %d is not found in the array \n", x);
	}
	else {
		printf("   %d is present in the array at index %d \n", x, idx);
	}

}

Output

The time complexity of recursive implementation is same as iterative (loop) implementation.

Advantages of Linear Search

1. It doesn’t depend upon the arrangement of elements in the array.
2. It works efficiently if the number of insertion operations is very large compared to search operations. Insertion in an unsorted array takes O(1) comparisons whereas insertion in the sorted array takes O(N) comparisons. If the number of insert/update operations is very large, then linear search performs better than binary search.
3. It can search for data in a linked list whereas binary search only applies to arrays.

Disadvantages of Linear Search

1. If the number of search queries is very large in comparison to insert/update then the program becomes very inefficient.

References

Wiki Sequential Search