/* Two versions of binary search */

#define size 50 /* size of the array to be searched */

/* input relevant libraries */
#include <stdio.h>

int search1 (int a [], int item) {
  /* program searches the sorted array a for item
     and returns the index if item or the
     location where item should be inserted to maintain ordering
  */

  /* Binary Search, Version 1 */
   int left = 0;
   int right = size - 1;
   int middle = (left + right + 1) / 2;  /* we must round up */
   while ((left <= right) && (a[middle] != item)) {
      if (a[middle] < item) 
         left = middle + 1;
      else
         right = middle - 1;
      middle = (left + right + 1) / 2;
   }

   return middle;
}


int search2 (int a [], int item) {
  /* program searches the sorted array a for item
     and returns the index if item or the
     location where item should be inserted to maintain ordering
  */

  /* Binary Search, Version 2 */
   int left = 0;
   int right = size;
   int middle = (left + right) / 2;  /* we must round up */
   while ((left < right) && (a[middle] != item)) {
      if (a[middle] < item) 
         left = middle + 1;
      else
         right = middle;
      middle = (left + right) / 2;
   }
   return middle;
}

void testBothSearches (int a [], int item) {
  /* use both search algorithms and print results */
  printf ("%5d  %5d", item, search1 (a, item));
  printf ("%8d\n", search2 (a, item));
}  

int main () {
  int a [size];
  int index;

  /* initialize a as a sorted array */
  for (index = 0; index < size; index++)
    a[index] = 2*index;

  printf ("item  search1   search2\n\n");

  /* test boundary conditions */
  printf ("testing boundary conditions\n");
  testBothSearches (a, -3);
  testBothSearches (a, 0);
  testBothSearches (a, 2*size-2);
  testBothSearches (a, 2*size+10);

  /* testing found and not found within the array */
  printf ("\ntesting within the array\n");
  testBothSearches (a, 5);
  testBothSearches (a, 6);
  testBothSearches (a, 7);
  testBothSearches (a, 8);

   }