Binary Search Using C Language

If in an array, the elements are placed in some order, for example a dictionary then there is an efficient searching algorithm, Binary search. In binary search the array will be reduced to small sub arrays while searching the element. Suppose we are searching an element N from an array ARR. First search for N at the middle of the array. If found then your searching is completed, otherwise check whether N is greater than or less than the middle value of the array. If less, then repeat the above process with first half the array otherwise repeat with the right half the array. This process will continue.

#include < stdio.h>

int bS(int target,int value[],int size)

{

  int mid,low=0,hi=size-1;

  while(low<=hi)

  {

     mid=(low+hi)/2;

   if(target > value [mid])

   low=mid+1;

   else if(target< value[mid])

   hi=mid-1;

   else

   break;

  }

  printf("\After executing the loop , mid=%d, value=%d, targer=%d",mid,value[mid],target);

  if(target==value[mid])

  return mid;

  else

  return -1;

  }

void main(void)

{

int array[] = {2,5,8,12,14,34,36,39,49,59},x,i;

clrscr();

printf("\nThe values are:-\n");

for(x=0;x<10;x++)

{

printf( "%d ",array[x]);

}

printf("\nEnter the value to be searched:-");

scanf("%d",&i);

x=bS(i,array,10);

if(x!=-1)

printf("\nSearch success,location is %d.",x);

else

printf("\nSearch not successful.");

getch();

}

Algorithm for Binary Search :-

ARR is the array where the values are stored. N is the number elements in the array.VAL is the element to be searched. LOW and HI are two variables storing the lower bound (0) and the upper bound (N-1) of the array.MID is another variable which will hold the middle position of the array and sub-array.

Repeat the following steps while (LOW<=HI)

Set MID=(LOW+HI)/2

If VAL < ARR[MID]

Set HI=MID-1

Else If VAL>ARR[MID]

Set LOW=MID+1

Else

Break the loop

[End of loop]

If VAL=ARR[MID]

Retrun True

Else

Return False

End

Complexity of binary search :-

The complexity of binary search is measured by the number of comparisons to locate an item from a number of elements; say N.I n binary search after each comparison, the size is reduced to half. Suppose we need maximum T comparisons to locate the element from the array, so 2T > N or 2T=N+1.so T=log2N+1.Ignoring the constant 1 ,we can say that T=log2N.So the complexity is O(log2N)