/**
 * ibs.c - An implementation of a simple binary search.
 */

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

#include "ibs.h"	
#include <stdio.h>


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

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


// +--------------------+---------------------------------------------
// | Exported Functions |
// +--------------------+

/**
 * ibs (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
ibs (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;
    
  // 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;
} // ibs