Monday, March 24, 2014

Binary Chop in C

#include <stdio.h>

int binchop (const int *a, int sz, int value)
{
   int first = 0;
   int last  = sz;

   while (first <= last)
   {
      int mid = (first + last)/2;  // <== potential overflow

      if (value < a[mid])
         last = mid - 1;
      else if (value > a[mid])
         first = mid + 1;
      else
         return mid;
   }
   return -1;
}

int binchop1 (const int *arr, int n, int key)
{
   int min = 0, max = n;
   while (min < max) {
      int middle = min + ((max - min) >> 1);  // overflow fixedmin + ((max - min) >> 1)
      if (key > arr [middle])
         min = middle + 1;
      else
         max = middle;
   }
   if (arr[min] == key) return min;
   else
   return -1;
}

int main()
{
   int A[] = {3, 4, 5, 10, 20, 21, 25, 29, 31, 35};
   int (*bchop) (const int *a, int sz, int value);

   bchop = & binchop;
   printf("%d\n", (*bchop)(A, 10, 20));

   bchop = & binchop1;
   printf("%d\n", (*bchop)(A, 10, 20));
   return 0;
}

No comments:

Post a Comment