/**
 * jqbs.c - An implementation of binary search, based on a version by
 *   Jesse Queen that was originally written in Python.
 */

#include "bs.h"

int
binary_search (int value, int values[], int count)
{
  int lo, hi;   // Boundaries of search space
  int mid;      // Middle of search space

  hi = count - 1;

  // Handle the special case of the empty array
  if (hi < 0)
    return -1;

  // More easily handle the special cases of one item array and first-item.
  if (value == values[0])
    return 0;

  // Find some boundaries
  lo = 0;
  mid = (lo + hi) / 2;
 
  // Stop the loop from terminating early
  hi = hi + 1;

  while ((hi != mid) && (mid != lo))
    {
      // If we've found the value ...
      if (value == values[mid]) 
        {
          return mid;
        }
      // If we can tell the value is in the lower half ...
      else if (value < values[mid])
        {
          hi = mid;
          mid = (hi+lo)/2;
        }
      // Otherwise, the value is in the upper half.
      else
        {
          lo = mid;
          // We'd like to round up when averaging, rather than round
          // down.  C rounds down.  We need to round up so that we can
          // reach the end.
          mid = (hi + lo + 1)/2;
        }
    }

  // Not found!
  return -1;
} // binary_search

/*
def binarysearch(i, vals):
        """Finds index of item i in list vals, assuming vals is in increasing order.
           Returns index of item if found, -1 if not found."""
        hi = len(vals)-1
        if(hi < 0): #empty list
                return -1
        if(i == vals[0]): #list with one item
                return 0  #or coincidentally first item
        lo = 0
        mid = (hi+lo)//2
        hi = hi+1 #keeps while loop from terminating before last index
        while(hi != mid and mid != lo):
                if(i == vals[mid]): #found it
                        return mid
                elif(i < vals[mid]): #i in lower half
                        hi = mid
                        mid = (hi+lo)//2
                else: #i in upper half
                        lo = mid
                        mid = round((hi+lo)/2+.1)
                        #Python sometimes rounds .5 down
                        #add .1 so it always rounds up
                        #otherwise end of list may not be reached
        return -1
*/