C Program to Implement Binary Search

General Introduction:

Binary Search is the more efficient searching technique compared to Linear Search. The binary search technique only takes 0(log n) times for n number of elements in an array.

However, it only works if the elements in an array are in sorted order( ascending or descending order).

Searching Technique:

Searching Technique:

• The middle of the array of items is calculated as m=(floor(l+r)/2) where l is the initial index of the array, r is the last index of the array.
• The searched item is compared with the element in the middle of the array.
• If a[m]==key, then the search is successful where the key is the searched element.
• If a[m]<key, then the searched element exists in the second half of the array.
• If a[m]>key, then the searched element exists in the first half of the array and is, therefore, is to be searched there only.

Example:

a[]={5,10,15,20,25,30,35,40,45,50}
Element to be searched( key)= 15.
Here, n=9(counting from 0)
l=0, r=9
Therefore, m=(floor(0+9)/2)=4.
a[m]=a[4]=25 (counting from 0).
Here, a[m]>key: so the element is to be searched in the first half of the array.

The first half of the array : a[]={5,10,15,20}
Element to be searched =15.
Here, n=3(counting from 0)
l=0, r=3
Therefore, m=(floor(0+3)/2)=1
a[m]=a[1]=10 (counting from 0).
Here, a[m]<key: so the element is to be searched is exist in the second half of the array.

The second half of the array: a[]={15,20}
Element to be searched =15.
Here, n=1(counting from 0)
l=0, r=1
Therefore, m=(floor(0+1)/2)=0
a[m]=a[0]=15(counting from 0).
Here, a[m]==key: so the element is to be searched is found in the array.

Code in C:

#include<stdio.h>
#include<conio.h>

int binary_search(int[],int,int,int);
int main()
{
	int a[20];
	int n;
	int key;
	int i;
	int value; /* to check if the element exist or not*/
	
	printf("How many items you want to insert in the array:");
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
	{
		printf("\nEnter %dth item: ",i+1);
		scanf("%d",&a[i]);
	}
	
	printf("\nEnter the item you want to binary search:");
	scanf("%d",&key);
	
	value=binary_search(a,0,n-1,key);
	if(value==1)
	{
		printf("Element %d exists in the array.",key);
	}
	
	else
	{
		printf("Element %d does not exist in the array.",key);	
	}
	getch();
	return(0);
	
}

int binary_search(int a[],int l,int r,int key)
{
	int m;
	if(l<=r)
	{
		m=(l+r)/2;
		
		if(a[m]==key)
		{
			return 1;
		}
		
		else if(a[m]<key)
		{
			return binary_search(a,m+1,r,key);
		}
		
		else
		{
			return binary_search(a,l,m-1,key);
		}
	}
	
	else
	{
		return -1;
	}
}

Outputs in C:

Do comment if you are confused in any steps.

Also Read: C Program to Find Gcd of Two Numbers using Iterative Euclid’s Algorithm