/* This program uses code from "Algorithms in C, Third Edition,"
 *               by Robert Sedgewick, Addison-Wesley, 1998.
 */

#include <stdio.h>

#define MAX_SIZE 10000

/* Determines if v is an element of S. 
 *  If yes, it returns the position of v in a.
 *  If not, it returns -1.
 *  N is the size of S.
 *  The function also prints the number of comparisons it made.
 */
int search(int S[], int N, int v)
{ 
  int left = 0; 
  int right = N-1;   
  int number_of_comparisons = 0;
  int result = -1;
  while (right >= left)
  { 
    number_of_comparisons++;
    int m = (left+right)/2;
    printf("m = %d, S[m] = %d\n", m, S[m]);
    if (v == S[m]) 
    {
      result = m;
      break;
    }
    if (v < S[m]) 
    {
      right = m-1; 
    }
    else 
    {
      left = m+1;
    }
  }
  printf("number of comparisons = %d, for an array of %d items\n",
         number_of_comparisons, N);

  return result;
}


/* usage: binary_search filename number_to_search
 * 
 * reads a set of numbers from the specified file.
 * checks to see if the specified number_to_search is 
 * included in that set.
 */
int main(int argc, char ** argv)
{
  int numbers[MAX_SIZE];
  int next_number, items_read, number_to_search;

  if (argc != 3)
  {
    printf("usage: binary_search filename number_to_search\n");
    return -1;
  }

  char * filename = argv[1];
  FILE * fp = fopen(filename, "rb");

  int counter = 0;
  while(1)
  {
    items_read = fscanf(fp, "%d", &next_number);
    if (items_read != 1) 
    {
      break;
    }    

    numbers[counter] = next_number;
    counter++;
    if (counter == MAX_SIZE)
    {
      break;
    }
  }
  fclose(fp);

  items_read = sscanf(argv[2], "%d", &number_to_search);
  if (items_read != 1)
  {
    printf("failed to read number_to_search from the command line\n");
    return -1;
  }

  int result = search(numbers, counter, number_to_search);
  printf("position of %d is: %d\n", number_to_search, result);
}