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 : START
2 : for i=1 to n do
3 : if(a[i]=K) then
4 : return i
5 : endIf
6 : endFor
7 : return 0
8 : 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 : START
2 : start=1
3 : stop=n
4 : middle=(start+stop)/2
5 : while(start<=stop) do
6 : if(list[middle]<K) then
7 : start=middle+1
8 : else if(list[middle]=K) then
9 : return middle
10 : else
11 : stop=middle-1
12 : endIf
13 : endWhile
14 : return 0
15 : 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

Heaven meets the Sea : GOA

Hello, have you ever been to GOA? No.....! Then you must read this article before planning for a vacation there. Ater reading this article you will be bound to move on.

More articles: Sea

Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: