#include "bsearch.h"

/*
 *  index_t  binsearch (a, lower, upper, key)
 *  KEY_T	a[];
 *  index_t	lower, upper;
 *  KEY_T	key;
 *
 *  Simple binary search:
 *
 *  Return (nonnegative) index of 'key' in array 'a[]' of KEY_T type.
 *  ['lower' .. 'upper'] is the range in which searching is performed.
 *  if 'key' was found, its index in 'a[]' (a nonnegative integer) is returned.
 *  -1 is returned if 'key' not found.
 *  -2 is returned if lower > upper on call.
 *
 *  Preconditions:
 *	lower <= upper and both are nonnegative integers.
 *	a[lower..upper] must be sorted.
 *
 *  (C) Copyright by Ariel Faigon,
 *  Released under the GNU GPL (General Public License) version 2
 *  http://www.gnu.org/licenses/licenses.html
 */
index_t binsearch (a, lower, upper, key)
KEY_T	a[];		/* array of values   */
index_t	lower, upper;	/* limit indices     */
KEY_T	key;		/* key value to search for */
{
	index_t	mid;	/* index of middle of range */

	if (lower > upper || lower < 0)	/* wrong call */
		return -2;

	while (lower <= upper) {
		mid = (lower + upper) / 2;
		if (a[mid] < key)
			lower = mid + 1;
		else if (a[mid] > key)
			upper = mid - 1;
		else		/* (a[mid] == key) -> found it */
			return mid;
	}

	return -1;	/* not found */
}