Linear Search

In this article, you'll learn searching and linear search algorithm.

Searching is a technique in which we find an element in the list or array of elements. If the found element in a list or array of elements, then this is a successful process. If the found element is not found in a list or array of elements then this is unsuccessful.

There is two most use searching algorithm in computer science are:

  1. Linear Search Algorithm
  2. Binary Search Algorithm
In this article, we only learn linear search and the binary search will cover in the next tutorial.

Linear Search

Linear Search

Linear search is also known as Sequential search. It works on both sorted and unsorted arrays. Linear search is a simple searching algorithm and it rarely uses an algorithm because it is a time-consuming algorithm and Binary Search Algorithm is a faster searching algorithm in terms of time complexity. We will learn about complexity in this article. 

Linear Search Algorithm

In this searching technique, We will slide the search element over the array elements. If the element is matched with the elements of the array then, we can say elements are present in the array. If the search element is not matched with any element of the array then, the element is not present in the array.

Now, you see the algorithm for linear search

linearSearch( Array 'A', Find 'X')

Step 0: Set i to 0
Step 1: if i > n-1 then go to step 6
Step 2: if A[i] == X then go to step 5
Step 3: Set i to i + 1
Step 4: Go to Step 1
Step 5: Search Element 'X' Found at index i and go to step 7
Step 6: Search Element Not Present in Array
Step 7: Exit


To know about linear search flowchart & implementation in C programming language, please click here ↗

Example:

C

In this example, linear search in C we take the same array as in the above image. so, if compare the image with code you'll easily understand the algorithm.
// Linear Search in C

#include <stdio.h>

int linearSearch(int Array[], int n, int X) {
  int i;
  for(i = 0; i < n; i++){
    if (Array[i] == X)
      return i;
	}
  return -1;
}

int main() {
   int n = 6;
   int Array[] = {3, 8, 12, 6, 10, 2};
   int X = 12;
   int result = linearSearch(Array, n, X);
    if(result == -1)
	 printf("Search Element Not Present in Array");
    else
	 printf("Search Element %d Found at index %d", X, result);
}


Complexity of Linear Search

The time complexity of the above algorithm is O(n).

Time Complexity:

  1. Best Case Complexity: O(1)                                                                                                                                         If the element is matched on the first index of the array then for loop work only 1 time then it takes less time that why this is the best case. 
  2. Average Case Complexity: O(n)
  3. Worst Case Complexity: O(n)                                                                                                                                      If the element is matched on the last index of the array then for loop work N times then it takes more time that why this is the worst case. 

Space Complexity:

Space complexity for linear search is always O(1).

We learn more about only complexity in another tutorial.

In this tutorial, you learn searching, linear search algorithm, and complexity of linear search in terms of time and space. I hope you enjoy this article.

Happy Coding 😊

No comments:

Post a Comment

If you have any doubts, Please let me know