#

#include	<stdio.h>


binsrch (item, base, nel, width, compar)

/* Perform a binary search for an item in a sorted array.  Returns the
 * index of the desired item in the array, or -1 if the item is not
 * present.  The algorithm follows Horowitz and Sahni, Fundamentals of
 * Computer Algorithms, Algorithm 3.3; but extended to take as an
 * argument a function for the element comparison operation and to
 * handle elements of any size.
 *
 * Arguments:
 */

char	*item;			/* pointer to item being searched for */
char	*base;			/* array of items to be searched */
				/* handled as char base[nel][width] */
int	nel;			/* number of items in array being searched */
int	width;			/* size of an item in bytes */
int	(*compar)();		/* ptr. to function to compare two items: */
				/* returns <, =, or > 0 */
{
	register int	elt;	/* index of element being considered */
	register int	bot;	/* index of bottom of current range */
	register int	top;	/* index of top of current range */
	int	v;		/* returned value from compare function */

	bot = 0;		/* bot <- bottom element */
	top = nel - 1;		/* top <- top element */
	while (bot <= top) {
		elt = (bot + top) >> 1; /* and try midpoint */
		if ((v = (*compar)(item, base + (width * elt))) == 0)
			return (elt);
		if (v < 0)	/* no, restrict range appropriately */
			top = elt - 1;
		else
			bot = elt + 1;
		}
	return (-1);
	}