# Search Techniques - Linear Search and Binary Search

Searching refers to finding an element in a list of elements. In this article, I am going to discuss about the two search techniques linear search and binary search with their corresponding algorithms and C programs.

## Linear Search

Linear Search is the simplest search technique. The procedure of linear search is as follows. The entire list is compared with the key element i.e. the element to be found and the search stops when the element is found. To understand linear search clearly, let us take an example.

Consider the list 23, 56, 22, 12, 90, 57, 78, 24, 88, 45, 70, 67, 34.
Consider the key element as 90.
Compare 23 & 90 (No Match - Continue)
Compare 56 & 90 (No Match - Continue)
Compare 22 & 90 (No Match - Continue)
Compare 12 & 90 (No Match - Continue)
Compare 90 & 90 (Match - End Linear Search)

### Algorithm for Linear Search

LinearSearch

`Input : An array a[1], a[2], …… a[n] and the key K.Output : The index of the array element which is equal to key K.1 : START2 : for i=1 to n do3 : if(a[i]=K) then4 : return i5 : endIf6 : endFor7 : return 08 : STOP`

### C Program for Linear Search

Program
#include<stdio.h>
#include<conio.h>
void main(void)
{
int size,list[25],key,i;
clrscr();
printf("\n Enter the number of elements : ");
scanf("%d",&size);
printf("\n Enter the list of elements : ");
for(i=1;i<=size;i++)
scanf("%d",&list[i]);
printf("\n Enter the element to search : ");
scanf("%d",&key);
for(i=1;i<=size;i++)
{
if(list[i]==key)
printf("\n Element found at position %d",i);
}
printf("\n Search Complete");
getch();
}

Output
Enter the number of elements : 13
Enter the list of elements : 23 56 22 12 90 57 78 24 88 45 70 67 34
Enter the element to search : 90
Element found at position 5
Search Complete

Time complexity for linear search is O(1) in the best case when the first element is equal to the key, O(n) in the average and worst cases when element not at the start or the last element is equal to the key respectively. Space complexity for linear search is O(n) in best, worst and average cases.

## Binary Search

As linear search takes a lot of time for large lists, binary search is introduced. The procedure of binary search is as follows. First, sort the list of elements and find the middle element. Compare the key element i.e. the element to be found with the middle element. If key is greater, apply binary search on the elements right to the middle element. If middle element is greater, apply binary search on the elements left to the middle element. To understand binary search clearly, let us take an example.

Consider the list 23, 56, 22, 12, 90, 57, 78, 24, 88, 45, 70, 67, 34.
Consider the key element as 90.
Sort the list to obtain 12, 22, 23, 24, 34, 45, 56, 57, 67, 70, 78, 88, 90.
Middle element is the 7th element i.e. 56.
Apply binary search on the list right (57, 67, 70, 78, 88, 90) to the middle element (90>56)
Middle element is the 3rd element i.e. 70.
Apply binary search on the list right (78, 88, 90) to the middle element (90>56)
Middle element is 2nd element i.e. 88.
Apply binary search on the list right (90) to the middle element (90>88)
Only one element is present and it is equal to 90.
Match - End Binary Search.

### Algorithm for Binary Search

BinarySearch

`Input : A sorted array a[1], a[2], …… a[n] and the key K.Output : The index of the array element which is equal to key K.1  : START2  : start=13  : stop=n4  : middle=(start+stop)/25  : while(start<=stop) do6  : if(list[middle]<K) then7  : start=middle+18  : else if(list[middle]=K) then9  : return middle10 : else11 : stop=middle-112 : endIf13 : endWhile14 : return 015 : STOP`

### C Program for Binary Search

Program
#include<stdio.h>
#include<conio.h>
void main(void)
{
int size,list[25],key,i,start,stop,middle;
clrscr();
printf("\n Enter the number of elements : ");
scanf("%d",&size);
printf("\n Enter the list of elements : ");
for(i=0;i<size;i++)
scanf("%d",&list[i]);
printf("\n Enter the element to search : ");
scanf("%d",&key);
start=0;
stop=size-1;
middle=(start+stop)/2;
while(start<=stop)
{
if(list[middle]<key)
start=middle+1;
else if(list[middle]==key)
{
printf("\n Element found at position %d",middle+1);
break;
}
else
stop=middle-1;
middle=(start+stop)/2;
}
printf("\n Search Complete");
getch();
}

Output
Enter the number of elements : 13
Enter the list of elements : 23 56 22 12 90 57 78 24 88 45 70 67 34
Enter the element to search : 90
Element found at position 5
Search Complete

Time complexity for above binary search is O(1), O(logn), O(logn) in best case, average case, worst case respectively. Space complexity for above binary search is O(1) in best, worst and average cases.

## Related Articles

#### Diseases through Drinking Water

Are you looking for information on Diseases through Drinking Water? Then find its complete detail.

#### Infectious Diseases And Vaccination Schedule for Child And Its Significance

Read this to know about Infectious Diseases And Vaccination Schedule for Child And Its Significance. The article describes the time for vaccination of Rubella, Chicken pox, Polio, Mumps, Measles etc.

More articles: Sea