program for binary search

// program for binary search.
 .#include
#include
int search(int[],int,int);                                                                    //binary search declaration
void main()
{
int a[20],n,item,p,i;
clrscr();
printf("Enter the limit\n");
scanf("%d",&n);
printf("Enter the array\n");
for(i=0;iscanf("%d",&a[i]);
printf("Enter the array to be searched\n");
scanf("%d",&item);
p=search(a,n,item);                                                                         //   binary search call
if(p==-1)
{
printf("sorry\n");
}
else{
printf("Item found at %d position",p+1);
}

getch();
}
int search(int a[],int n, int item)                                                                //   binary search definition
{
int beg=0,end=n-1,mid;
while(beg<=end)
{
mid=(beg+end)/2;
if(a[mid]==item)
{
return mid;
 }
else if(item>a[mid])
{
beg=mid+1;
}
else
{
end=mid-1;
}
}
return -1;
}

 A fast way to search a sorted array is to use a binary search. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.

Algorithm

Algorithm is quite simple. It can be done either recursively or iteratively:

1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
   • searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
   • searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

Now we should define, when iterations should stop. First case is when searched element is found. Second one is when sub array has no elements. In this case, we can conclude, that searched value doesn't present in the array.

 // program for binary search.
 // program for binary search.