//  Program Name: search.c

//  Purpose: Demonstrates slow, medium, and fast searches.

//  Search types:  1) sequential;  2) binary;  3) one_lookup search
//  These search methods can be used against huge amounts of data.
//  In this program, a small amount of data is used and the code
//  is simplified for easy reading.

//  This program was created by   Scott Wenger
//                                Box 802
//                                Stevens Point, WI 54481  USA
//                                panther@wctc.net

//  I've always believed that having one page of source code
//  (that works) is more valuable than having over a hundred
//  pages of text about programming concepts.  This program 
//  is provided in that spirit.

//  This program uses standard header files.
//  My compiler required the following header files:

#include <stdio.h>  
#include <stdlib.h>   
#include <string.h>   
#include <float.h>    
#include <conio.h>        // for getch()

#define TOTAL_RECORDS 15  // maximum number of items (or records) in storage

// function prototypes
int sequential(int item, int *ptr, int max);    // slow search 
int binary(int item, int *ptr, int max);        // medium-speed seach
int one_lookup(int item);                       // fast search / retrieval
int index();                                    // for one_lookup function

//  globals
int storage[] = {  1,   3,  17,  23,   84, 
                 255, 257, 301, 649,  711, 
                 893, 905, 916, 925, 1000 };
int number = 925;     // a number in the storage array (above)
int *store;           // for use by one_lookup function


int index()
{
  int i, temp;

  store = (int *) malloc(1001);    // allocate some memory
  memset(store, '\0', 1001);       // set allocated memory to NULLS

  for (i = 0; i < 15; i++) {
    temp = storage[i];             // obtain value in storage
    *(store + temp) = i;           // store location of items in memory
  }	      
  return(1);
}


int sequential(int item, int *ptr, int max)   // slow search
{
  // Sequential function returns 0 if item is not found.
  // Otherwise, function returns number of places checked before 
  // the item was found
	
  int i;
  int retval = 0;                     // item not found yet
  for (i = 1; i < max + 1; i++) { 
    if (*ptr++ == item)  retval = i;  // item was found after retval tries      
  }
  return(retval);
}  


int binary(int item, int *ptr, int max)
{
  // This sort requires the data to be sorted
  // Binary function returns 0 if item is not found.
  // Otherwise, function returns number of places checked before 
  // the item was found.

  int lo, hi, mid;
  int guess = 0;

  lo = 0;
  hi = max - 1;

  while (lo <= hi) {
    mid = (int)  (lo + hi) / 2;
    guess++;
        
    if (item == *(ptr + mid) ) {  // item found at "mid"
      return(guess + 1);          //  return number of places searched
    }	    
    if (item < *(ptr + mid) ) {   // (actual is lower)
      hi = mid - 1;               // because item < *(ptr + mid)
    }	    
    else {                        // (actual is higher)
      lo = mid + 1;               // because item > *(ptr + mid)
    }      
  }
  return(0);                      // item not found    
}



int one_lookup(int item)          // fast search (retrieval)
{
  // This function uses an index for immediate retrieval.
  // The index was created in memory (by the index function.)
  // Function returns 0 if item is not found.
  // Otherwise, function returns number of places checked before 
  // the item was found.

  int place;
  int retval = 0;                 // assume not found at first
     
  if ( *(store + item) >=  0) {
    place = *(store + item);      // found at position "place" (in memory)
    retval = 1;                   // item found immediately using index
  }    	
  return(retval);
}


main()
{
  int item;                  // the search item (the item to find)
  int *ptr;                  // a pointer to integer
  int max = TOTAL_RECORDS;   // the number of items in storage
  int r1, r2, r3;            // number of places searched until item is found
  int i;

  r1 = r2 = r3 = 0;  
  ptr = storage;             // ptr now points to start of storage
  item = number;             // the item to search for is variable "number"

  for (i = 0; i < 80; i++) printf("\n");  // primitive clear screen
  printf("   ------ Search Methods: Sequential, Binary, & One-Look Up ------\n");
  printf("\n   The array  \"storage\" was declared & initialized as follows:\n");      
  printf("\n   int storage[] = {  1,   3,  17,  23,   84, ");
  printf("\n                    255, 257, 301, 649,  711,  ");
  printf("\n                    893, 905, 916, 925, 1000 }; \n");

  index();                           // create index for one_lookup function
 
  r1 = sequential(item, ptr, max);   // slow search of storage
  r2 = binary(item, ptr, max);       // medium-speed search of storage 
  r3 = one_lookup(item);             // fast search (immediate retrieval)
 
  if (r1 == 0 && r2 == 0 && r3 == 0) {  
    printf("\n   The search item was not found.\n\n");
    free(store);
    exit(0);
  }

  printf("\n   In this example, the number %d is the search item to find.", item);
  printf("\n   The program uses sequential, binary, and one-lookup");
  printf("\n   search methods to find that item in the storage array.\n");
 
  
  if (r1 != 0)
    printf("\n   Sequential search method checked %d places before finding item %d", r1, item);

  if (r2 != 0)
    printf("\n   Binary search method checked %d places before finding item %d", r2, item);  

  if (r3 != 0)
    printf("\n   One_lookup search method checked %d place to find item %d", r3, item);

  if (r1 > r2 || r1 > r3) 
     printf("\n\n   In this particular example, search speed is as follows:\n");
  if (r1 > r2)
    printf("\n       [] Binary search was %.2f times faster than sequential search.", (float) r1 / r2);  
  if (r1 > r3)
    printf("\n       [] One_lookup method was %.2f times faster than sequential search.\n",  (float) r1 / r3);
      
  free(store);  // free memory allocated by index function
  printf("\n   Press any key to return to your operating system...\n");
  getch();
  exit(0);
}