# 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=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=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=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;
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;
}
}
``````