/**
 * 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


// +-----------+------------------------------------------------------
// | 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 (int x, int 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 - 1;
    
  // 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 = %d, low = %d, mid = %d, high = %d\n",
                  x, low, mid, high);
        }
      // Does x belong in the left half?
      if (x < v[mid])
        high = mid - 1;
      // Does x belong in the right half?
      else if (x > v[mid])
        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

/**
 * looks_like_int(str) 
 *   Determine if the string looks like an integer.
 */
int
looks_like_int (char *str)
{
  int i = 0;

  // Skip over leading sign.
  if ((str[0] == '+') || (str[0] == '-'))
    ++i;

  // Consider remaining characters.
  while (str[i] != '\0')
    {
      if (! isdigit (str[i]))
        return 0;
      ++i;
    } // while

  // We've read through all the characters.  It must be an integer.
  return 1;
} // looks_like_int

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


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

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

  // Sanity check
  if (argc < 2)
    {
      printf ("Usage: %s X V0 V1 ... VN-1\n", argv[0]);
      return -1;
    }

  // Grab x
  if (! looks_like_int (argv[1]))
    {
      printf ("Invalid X.  Given %s, expected an integer.\n", argv[1]);
      return 1;
    }
  x = atoi (argv[1]);

  // Build v
  for (i = 2; i < argc; i++)
    {
     if (! looks_like_int (argv[i]))
       {
         printf ("Invalid V[%d].  Given %s, expected an integer.\n", 
                 i-2, argv[i]);
         return i;
       }
      v[i-2] = atoi (argv[i]);
    } // for

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

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

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