/***
*bsearch.c - do a binary search
*
*	Copyright (c) 1985-1992, Microsoft Corporation. All rights reserved.
*
*Purpose:
*	defines bsearch() - do a binary search an an array
*
*Revision History:
*	07-05-84  RN	initial version
*	06-19-85  TC	put in ifdefs to handle case of multiplication
*			in large/huge model.
*	04-13-87  JCR	added const to declaration
*	08-04-87  JCR	Added "long" cast to mid= assignment for large/huge
*			model.
*	11-10-87  SKS	Removed IBMC20 switch
*	12-11-87  JCR	Added "_LOAD_DS" to declaration
*	01-21-88  JCR	Backed out _LOAD_DS...
*	02-22-88  JCR	Added cast to get rid of cl const warning
*	10-20-89  JCR	Added _cdecl to prototype, changed 'char' to 'void'
*	03-14-90  GJF	Replaced _cdecl with _CALLTYPE1, added #include
*			<cruntime.h>, removed #include <register.h> and fixed
*			the copyright. Also, cleaned up the formatting a bit.
*	04-05-90  GJF	Added #include <stdlib.h> and #include <search.h>.
*			Fixed some resulting compiler warnings (at -W3).
*			Also, removed #include <sizeptr.h>.
*	07-25-90  SBM	Removed redundant include (stdio.h), made args match
*			prototype
*	10-04-90  GJF	New-style function declarator.
*
*******************************************************************************/

#include <cruntime.h>
#include <stdlib.h>
#include <search.h>

/***
*char *bsearch() - do a binary search on an array
*
*Purpose:
*	Does a binary search of a sorted array for a key.
*
*Entry:
*	const char *key    - key to search for
*	const char *base   - base of sorted array to search
*	unsigned int num   - number of elements in array
*	unsigned int width - number of bytes per element
*	int (*compare)()   - pointer to function that compares two array
*		elements, returning neg when #1 < #2, pos when #1 > #2, and
*		0 when they are equal. Function is passed pointers to two
*		array elements.
*
*Exit:
*	if key is found:
*		returns pointer to occurrence of key in array
*	if key is not found:
*		returns NULL
*
*Exceptions:
*
*******************************************************************************/

void * _CALLTYPE1 bsearch (
	REG4 const void *key,
	const void *base,
	size_t num,
	size_t width,
	int (_CALLTYPE1 *compare)(const void *, const void *)
	)
{
	REG1 char *lo = (char *)base;
	REG2 char *hi = (char *)base + (num - 1) * width;
	REG3 char *mid;
	unsigned int half;
	int result;

	while (lo <= hi)
		if (half = num / 2)
		{
			mid = lo + (num & 1 ? half : (half - 1)) * width;
			if (!(result = (*compare)(key,mid)))
				return(mid);
			else if (result < 0)
			{
				hi = mid - width;
				num = num & 1 ? half : half-1;
			}
			else	{
				lo = mid + width;
				num = half;
			}
		}
		else if (num)
			return((*compare)(key,lo) ? NULL : lo);
		else
			break;

	return(NULL);
}