Binary Search

Binary search technique is more efficient than the linear search. In binary search each and every element is not traversed to find the required element.
The main limitation of binary search technique is that it can process only sorted data.The data need to be in sorted form so that binary search can be applied to it.If data is not sorted then it needs to be sorted first.
In Binary search the middle element is found first. Basically there are three values required.
Upper_bound (ub),Lower_bound(lb),Middleelemnt(mid)
mid=(ub+lb)/2;
if the middle element is less than the element to be searched then
lb=mid+1..
 and id middle element is greater than the element to be searched then.
ub=mid-1;

Program for Binary Search

#include<stdio.h>
#include<conio.h>
void main()
{
int a[10];
int flag,n,i,item,mid,lb,ub;
clrscr();
printf("Enter the number of elements you wnat to enter");
scanf("%d",&n);
printf("\nEnter the elements of arrayin sorted form\n");
for(i=0;i<n;i++)
{
 printf("a[%d] =",i);
 scanf("%d",&a[i]);
}

printf("\nThe elements of array are");
for(i=0;i<n;i++)
{
 printf("\na[%d] = %d",i,a[i]);
}

printf("\nEnter the elements of array to be searched");
scanf("%d",&item);

lb=0;
ub=n-1;
while(ub>=lb)
{
mid=(ub+lb)/2;

if(item==a[mid])
{
flag=1;
break;
}
else
{
if(item>a[mid])
{
 lb=mid+1;
}
else
{
ub=mid-1;
}
}
}
if(flag==1)
{
printf("\n Item %d found at location a[%d]",item,mid);
}
else
{
printf("\nItem not found");
}
getch();
}