C program for Binary Search

Binary search is used to find the position of a key in a sorted array. The following describes the binary search algorithm:

• We compare the key with the value in the middle of the array. If the key match found, we return its position, which is the index of the middle element of the array.
• If the key is less than the value of the middle element of the array, we repeat the above step on the sub-array on the left. 
• If the key is greater than the value of the middle element of the array, we repeat the above step on the sub-array on the right.
• If the sub-array to be searched has zero item, it means the key cannot be found.

C Program:

#include<stdio.h>

void main()
{
   int n, i, key, flag = 0, low, high, mid;
   printf("Enter the size of array\n");
   scanf("%d", &n);
   int a[n];
   low = 0;
   high = n-1;
   printf("Enter %d elements\n", n);
   for(i=0; i < n; i++)
       scanf("%d", &a[i]);
   printf("Enter the element to search\n");
   scanf("%d", &key);
   mid = (low + high)/2;
   while(low<=high)
     {
        if(a[mid] == key)
        {
          printf("%d found at location %d.\n", key, mid+1);
           break;
         }
      else if(key < a[mid])
            high = mid - 1;
      else
           low = mid + 1;
     mid = (low + high)/2;
    }
  if(low>high)
     printf("Element not found");

}

Output:

Enter the size of array                                                                                                                              

5                                                                                                                                                    

Enter 5 elements                                                                                                                                     

11                                                                                                                                                   

33                                                                                                                                                   

55                                                                                                                                                   

77                                                                                                                                                   

99                                                                                                                                                   

Enter the element to search                                                                                                                          

55                                                                                                                                                   

55 found at location 3.