/*	Test driver for chapter 2 searches
	Written by: G & F
	Date:       2/98
	
	Copyright 1998
  Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	All Rights Reserved
*/
#include <stdio.h>

/*	Constants */
	const int SIZE = 100;

/*	Prototype Declarations */
int binarySearch   (int list[ ], int end, int target, int *locn);

int main (void)
{
/*	Local Declarations */
	int  i;
	int  list[SIZE];
	int  srchArgu;
	int  foundLocn;
	
/*	Statements */
	printf ("Demonstrate Binary Search\n\n");
	
	/* Fill Array */
	for (i = 0; i < SIZE; i++)
		list[i] = 2 * i;
		
	printf ("You may search the following array: ");
	for (i = 0; i < SIZE; i++)
	    {
	     if (!(i % 10))
	         printf("\n");
	     printf ("%4d", list[i]);
	    }
	printf ("\n");
	
	printf ("\nEnter a number in the list: ");
	scanf  ("%d", &srchArgu);
	i = binarySearch (list, SIZE - 1, srchArgu, &foundLocn);
	if (i)
	     printf ("Found %d @ index location %d\n", list[foundLocn], foundLocn);
	else
	     printf ("Did not find %d\a\n", srchArgu);
	
	printf ("\nEnter a number not in the list: ");
	scanf  ("%d", &srchArgu);
	i = binarySearch (list, SIZE - 1, srchArgu, &foundLocn);
	if (i)
	     printf ("Found %d @ index location %d\n", list[foundLocn], foundLocn);
	else
	     printf ("Did not find %d\a\n", srchArgu);
	
	return 0;
}	/* main */

/*	Search an ordered list using Binary Search 
	Pre:	list must contain at least one element
			end is index to the largest element in the list
			target is the value of element being sought
			locn is address of index in calling function
	Post:	FOUND: locn = index to target element 
				   return 1 (found)
			NOT FOUND: locn = index below or above target 
					   return 0 (not found)
*/
int binarySearch   (int list[ ],
                    int end,
                    int target, 
                    int *locn )
{
/*	Local Declarations */
	int first ;
	int mid ;
	int last ;

/*	Statements */
	first = 0 ;
	last = end ;
	while ( first <= last )
		{
		 mid = ( first + last ) / 2 ;
		 if ( target > list[ mid ] )
			/* look in upper half */
			first = mid + 1 ;
		else if ( target < list[ mid ] )
				/* look in lower half */
				last = mid - 1 ;
		else
				/* found equal: force exit */
				break ;
		}	/* end while */
	*locn = mid ;
	return (target == list [mid]) ;
}	/* binarySearch */

/* Results
	Demonstrate Binary Search

	You may search the following array: 
	   0   2   4   6   8  10  12  14  16  18
	  20  22  24  26  28  30  32  34  36  38
	  40  42  44  46  48  50  52  54  56  58
	  60  62  64  66  68  70  72  74  76  78
	  80  82  84  86  88  90  92  94  96  98
	 100 102 104 106 108 110 112 114 116 118
	 120 122 124 126 128 130 132 134 136 138
	 140 142 144 146 148 150 152 154 156 158
	 160 162 164 166 168 170 172 174 176 178
	 180 182 184 186 188 190 192 194 196 198

	Enter a number in the list: 80
	Found 80 @ index location 40

	Enter a number not in the list: 199
	Did not find 199
*/