/*	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>
#include <stdlib.h>

/*	Constants */
#define SIZE 100

/*	Prototype Declarations */
int seqSearch   (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 */
	srand(997);
	for (i = 0; i < SIZE; i++)
		list[i] = rand() % 500;
		
	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 = seqSearch (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 = seqSearch (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 */


/*	Locate the target in an unordered list of size elements.
	Pre:	list must contain at least one item.
			last is index to last element in the list
			target contains the data to be located
			locn is address of index in calling function
	Post:		FOUND:		matching index stored in locn address
				  	        return 1 (found)
			    NOT FOUND:	last stored in locn address.
						    return 0 (not found)
*/
int seqSearch   (int list[ ], 
                 int last, 
                 int target, 
                 int *locn )
{
/*	Local Declarations */
	int looker ;

/*	Statements */
	looker = 0; 
	while ( looker < last && target != list[looker] )
		 looker++ ; 

	*locn = looker ;
	return ( target == list[looker] ) ;
}	/* seqSearch */

/*	Results
	Demonstrate Binary Search

	You may search the following array: 
	  75 303 276 437  36 361 157  79 179 126
	  10 407 463 334 378 182 197 411 330 254
	 107 377 295  61  48 486 201  43  99 420
	 309 321 457 374 433 391 201 173 420 382
	  33 399 234 274 309 110 246 226 258 245
	 169 263 304  16 305  22 369 261 488 364
	  97 478 347 446 387 202 435 264  13  77
	 103 459  43 271 340  86 377 420  31 363
	  72 441 272 370 246 103  71 381 365 336
	 179 133 374 322 462 331 195  55 342   4

	Enter a number in the list: 4
	Found 4 @ index location 99

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