Saturday, 3 January 2015

C Program for implementing Binary Search

 In this post we will discuss on a basic searching technique called as binary search . It searches an element (generally called a key ) from a sorted array. The array is divided into 2 sub arrays one from middle to start and other sub array from middle to end. If the sorted array is in ascending order and the key element is greater than the middle it searches the right sub array else left sub array and the same process continues in those sub arrays until the key element is found.
PROGRAM :

```#include <stdio.h>
#include <stdlib.h>

int main()
{
int i, first, last, middle, n, key, array;

printf("How many elements ?\t");
scanf("%d",&n);

for ( i = 0 ; i < n ; i++ )
{
printf("\nEnter number %d :\t", i+1);
scanf("%d",&array[i]);
}

printf("\nEnter value to find\t");
scanf("%d",&key);

first = 0;
last = n - 1;
middle = (first+last)/2;

while( first <= last )
{
if ( array[middle] < key )
first = middle + 1;
else if ( array[middle] == key )
{
printf("%d found at position %d.\n", key, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last)/2;
}
if ( first > last )
return 0;
}
```

OUTPUT :

Note : The input here  is in ascending order