Linear Search

Searching Algorithm

Share

About

In this searching technique we compare the elements of the array one-by-one with the key element we are looking for. It is a very simple searching algorithm but takes a lot of time. If the key element is present in the array then the search is successful else not.

  • Linear search is also known as sequential search.
  • If there are n elements in the array then, in the best case key is found in 1 comparison. While in the worst case it takes n comparison.
  • Best case occurs when the key is at first position of the array.
  • In the worst case the key element is either at the last position or not present in the array.

Pseudo code


/*a[0:n-1] is an array of n elements. key is the element being searched.
*/
LinearSearch(a,n,key)
Begin
    for i = 0 to n-1 by 1 do
        if a[i] == key then
	return i;		//returning index of the array
        endif
    endfor
    return -1;	//key not found
End

Order of Linear Search

In the best case scenario we will find the element we are searching for in 1 comparison.
That is, the first element is the answer.
So, O(1)

In worst case the element we are looking for is either at the last position or not present and thus we have to make n comparisons.
So, O(n)

Linear search code in C


#include 

//function declaration
int linearSearch(int *a, int n, int key);

int main(){
	//variable declaration
	int arr[5], i, key;
	
	//input
	printf("Enter the array elements: ");
	for(i = 0; i < 5; i++)
		scanf("%d", &arr[i]);
	printf("Enter key: ");
	scanf("%d", &key);
	
	//search
	i = linearSearch(arr, 5, key);
	
	//output
	if(i == -1)
		printf("Key not found.\n");
	else
		printf("Key at index: %d\n", i);
		 	
	return 0;
}

//function definition
int linearSearch(int *a, int n, int key){
	int i;
	for(i = 0; i <= n-1; i++){
		if(a[i] == key)
			return i;
	}
	return -1;
}

Recently Added