/*
 * By  Ronald E. Jacobs.
 * For Allen Holub's C for Professionals class.
 *     October 22, 1990.
 *     Homework 5.
 * File name: 
 *      int     *search(array, key, array_size, stackspace)
 *      int     *array, key, array_size, *stackspace;
 * What it does: A recursive binary search in the array for the integer key.
 *      Returns a pointer to the cell in which the key is found or -1 if the
 *      key is not in the array.  Returns NULL if its use of stack space
 *      exceeds stackspace.  *stackspace holds the address of a variable 
 *      local to the calling subroutine.  On entry, *stackspace should hold
 *      the maximum amount of run-time stack (in bytes) that search() may
 *      use.
 * How it does it: The array must be sorted in ascending order.  
 *	Compare the key to a value in the middle of the array. 
 *	If key is found during a compare, return a pointer to 
 *	the cell in which it was found.  If key is larger than or
 *	smaller than the value checked, then check a middle value 
 *	in the remaining upper or lower half of the array.  
 */


/*----------------------------------------------------------------*/


#include <stdio.h>

static int iteration1;		/* flag == 0 if on first iteration	*/

int     *search(array, key, array_size, stackspace)
int     *array, key, array_size, *stackspace;

{
        int     halfsize;	/* 1/2 the size of the array            */
        int     test_el;	/* array element being compared to key  */
	int	stackallowed;	/* Maximum amount of stack allowed	*/
	int	stackused;	/* total amount of stack used		*/

	if (iteration1)		/* iteration1==0 only on 1st iteration  */
	{
		stackallowed = *stackspace;
		*stackspace = &stackspace; /* arbitrary stack reference point */
		iteration1 = 1;       /* don't execute these statements again */
	}
	
	stackused = &stackspace - stackspace;
	
	if (0 >= stackallowed - *stackspace)	/* if stack allotment used up */
	{
		return(NULL);			/* error return */
	}

        if (array_size <= 0)	/* key not found */
	{
		*stackspace = stackused;
                return (int *) -1;
        }
	
        halfsize = array_size/2;
        test_el = *(array + halfsize);

        if (key > test_el)
        {
                array += halfsize + 1;
                array_size = (array_size - 1)/2;
        }
        else if (key < test_el)
        {
                array_size = (array_size / 2);
        }
        else                    /* element tested == key: it's found! */
        {
		*stackspace = stackused;
                return (array + halfsize);
        }
        search(array, key, array_size, stackspace);     /* recursive search */
}

/*--------------------------------------------------------------------*/

/*
 * The purpose of main() is to test search().
 */


static int     array[] = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12};

main()
{
        int     key;
        int     array_size;
        int     *stackspace;
        int     *found_at;
	int	maxstack;	/* bytes of stack search() is allowed to use */

        key = 8;
        array_size = 11;
        maxstack = 100;
	stackspace = &maxstack;

        found_at = search(array, key, array_size, stackspace);
        printf("The value %d is in the element at address ", key);
        printf("%#x\n", found_at);
}