/*
  A simple example of binary search using parallel arrays of students 
  heights and names.  Query the user for a height, search for that
  height and report the student's name if found.
*/

#include <stdio.h>
#include "genlib.h"
#include "simpio.h"

#define Students 10

int BinarySearchForInteger(int target, int array[], int n);
bool IntegerArrayIsSorted(int array[], int n);

main() {
  int heights[Students] = {48, 49, 54, 55, 59, 60, 61, 62, 63, 64};
  string names[Students] = {"John", "Lane", "Lisa", "Gary", "Amy",
			    "Steve", "Sally", "Horace", "Sean", "Hector"};
  int find, result;

  if (!IntegerArrayIsSorted(heights, Students))
    Error("The array must be sorted to use binary search.\n");
  printf("Enter a height to search for> ");
  find = GetInteger();
  result = BinarySearchForInteger(find, heights, Students);
  if (result != -1)
    printf("%s is %d inches tall.\n", names[result], find);
  else
    printf("No one in the class is %d inches tall.\n", find);
}
  
// return index of target, or -1 if not found
// NOTE: array must be sorted for binary search to work properly
int BinarySearchForInteger(int target, int array[], int n) {
  int low, high, mid;

  low = 0;
  high = n-1;
  while (low <= high) {
    mid = (low+high)/2;
    if (target == array[mid])
      return mid;
    else if (target < array[mid])
      high = mid-1;
    else
      low = mid+1;
  }
  return(-1);
}

// Implement this.
// Returns TRUE when the given array is in sorted order.
// Otherwise returns FALSE.
bool IntegerArrayIsSorted(int array[], int n) {
 
  return(TRUE);
}