/**
 * binsearch X V0 V1 ... VN
 *   Search for X in [V0,V1,V2,...,VN]
 *
 * Based on example on p. 58 of K&R 2nd edition.
 *
 * Disclaimer: This program does not do significant error checking.
 */

// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>	// For printf
#include <stdlib.h>	// For atoi
#include <string.h>	// For strcmp


// +-----------+------------------------------------------------------
// | Constants |
// +-----------+

/**
 * Are we testing our program, which means we want extra output?
 */
#define TESTING 0


// +-----------+------------------------------------------------------
// | Utilities |
// +-----------+

/**
 * binsearch (x, v[], n)
 *   Find the index of x in the sorted array v of size n.
 *   Return -1 if the value is not found.
 */
int
binsearch (char x[], char *v[], int n)
{
  int low;      // The low end of the part we're searching
  int high;     // The high end of the part we're searching
  int mid;      // Tee middle of the part we're searching

  // Initially, we want to search the whole array
  low = 0;      
  high = n;
    
  // Continue searching parts of the array until we find the
  // element (return in the middle) or we run out of elements
  // to look at.
  while (low <= high)
    {
      mid = (low+high) / 2;     // Potential bug, but ok for now
      if (TESTING)
        {
          printf ("x = %s, low = %d, mid = %d, high = %d\n",
                  x, low, mid, high);
        }
      // Does x belong in the left half?
      if (strcmp (x, v[mid]) < 0)
        high = mid - 1;
      // Does x belong in the right half?
      else if (strcmp (x, v[mid]) > 0)
        low = mid + 1;
      // Otherwise, x is v[mid]
      else
        return mid;
    } // while (low <= high)

  // Since we've looked at the whole array, the value isn't there.
  return -1;
} // binsearch

/**
 * print_vector(v, n)
 *   Print a vector of ints
 */
void
print_vector (char *v[], int n)
{
  int i;	// A counter variable.  What else?
  printf ("{");
  if (n > 0)
    {
      printf ("%s", v[0]);
      for (i = 1; i < n; i++)
        printf (",%s", v[i]);
    } // if (n > 0)
  printf ("}");
} // print_vector


// +------+-----------------------------------------------------------
// | Main |
// +------+

int
main (int argc, char *argv[])
{
  char *x;                // The value we're searching for
  int n = argc-2;       // The size of the vector we're searching
  char *v[n];             // The vector to search
  int i;                // Everyone's favorite counter variable
  int index;            // The index of x in v.

  x = argv[1];

  // Build v
  for (i = 2; i < argc; i++)
    v[i-2] = argv[i];

  // Find the index of x
  index = binsearch (x, v, n);

  // Print the result
  if (index == -1)
    {
      printf ("Could not find %s in the vector ", x);
      print_vector (v, n);
      printf ("\n");
    } // if not found
  else
    {
      printf ("The index of %s in the vector ", x);
      print_vector (v, n);
      printf (" is %d.\n", index);
    } // if found

  // And we're done
  return 0;
} // main