Linear Search

Linear search also known as sequential search is a search algorithm used in various data structures to find the key position of a element.

This search algorithm works on a array (sorted or unsorted) and returns the position of value which user wants to know.

It compares all the elements sequentially with the key value which we are looking for.

Once we have a match it returns the position at which it found the value.

If we don't get any match then the key value which we are looking for doesn't exist.

Unlike Binary search, it is not important to have a sorted array in linear search.

Binary search cannot be used in case of linked lists, So in that case linear search is very useful.

---

Example:

Array[] = {23, 12, 35, 10, 76, 48}

Key value is 10

First the comparison is done between the first value and the key value.

i.e 23 = 10

Since it's false,

We will move to the next value in the sequence and compare it with the key value.

Same process will be repeated until we have a match or there are no other elements to compare.

If we have a match then the position at which the match is found is returned.

Else, a message is displayed that the element which we are looking for doesn't exist in the sequence.

In above case,

We have a match at position 4 (where 10=10)

---

Implementation using C: Iterative

#include <stdio.h> 
  
int linear_search(int arr[], int n, int x) 
{
	int i; 
 	for (i = 0; i < n; i++) 
 	if (arr[i] == x) 
  		return i;
	// If x is present then return its location
 		return -1;
	// otherwise return -1  
} 
  
int main(void) 
{ 
 	int arr[] = {23,12,35,10,76,48}; 
 	int x = 10; 
 	int n = sizeof(arr) / sizeof(arr[0]); 
 	int result = linear_search(arr, n, x); 
 	if(result == -1)
 	 {
 	    printf("Element is not present in array"); 
 	 }
 	else
 	{
 	   printf("Element is present at index %d",result);
 	} 
 	return 0; 
}

Output:
Element is at index 3.

---

Miscellaneous:

Worst-case time complexity = O(n)

Best-case time complexity = O(1)

Average time complexity = O(n)

Worst-case space complexity = O(1) for iterative

For more click here.

Follow for more tech blogs #programmersdoor #searching #datastructures