C Programming Challenge #07: Search - binary

Binary search is one of the simple searching technique. It can search only on sorted array. As the name suggests binary means 2, here it is referring to dividing the array into two equal parts.

 It is best illustrated by an example. 12 is the key we are searching in a sorted array.

First mid point of entire array is taken and compared against key. Key 12 is greater than 8, hence only possibility is that it should be in second half of the array. It cannot be in first half since all the elements in first half are <= 8. Hence in the first round almost half the elements are eliminated. In second round the mid point of the sub-array is found and same thing is continued till the key is either found or not found.

Lets implement it as function so that it can be easily used later.
Strategy:

• Assuming variable arr is pointer to array where numbers are placed.
• Variable max will hold the maximum array index.
• Variable key will hold the key that needs to be searched.
• Each array/sub-array will be recognized by where it will start, end and middle point.

#include <stdio.h>

int search_binary(int *, int, int);

int main()
{
   int a[] = {2, 4, 5, 8, 9, 12, 15};
   int key = 12;
   int found_index;
 
   found_index = search_binary(a, 6, key);

   printf("%d key is found in index %d\n", key, found_index);

   return 0;
}

int search_binary(int *arr, int max, int key)
{
   int start, middle, end;
   
   start = 0;
   end = max;
   middle = (start + end) / 2;

   do {
      if(key > a[middle]) {
         /* Search in Top half*/
         start = middle + 1;
      } else if (key < a[middle]) {
         /* Search in Bottom half */
         end = middle - 1;
      } else {
         /* Found the index */
   break;
      }
      middle = (start + end) / 2;
   }while (start < end);

   /* By this we would have search
      is complete successfully or not */    
   if(start <= end) {
     /* Successful */
     return middle;
   }else {
     /* Not Successful */
     return -1;
   }
}

Output of above program is

12 key is found in index 5

If in case key was not found, then index would be -1, which is invalid.

Links

Next Article - C Programming Challenge #08: Sort - insertion (binary search variant)
Previous Article - C Programming Challenge #06: Sort - insertion (using recursion)
All Article - C Programming Challenge