/*  Demonstration of how one could use a binary search algorithm
    to look up a student's name given his ID number.  A group of
    records is read in, and then sorted.  Then, the user supplies
    the key for the search (a sample ID #), and the list is searched
    with a binary algorithm.  */

#include<stdio.h>
#include<stdlib.h>

#define MAXSTUDENTS 50    /*  Declaration statement */

void id_swap(long int *k, long int *l)
{
  long int temp;

  temp = *k;
  *k = *l;
  *l = temp;
}

void grade_swap(int *grade1, int *grade2)
{
  int temp;

  temp = *grade1;
  *grade1 = *grade2;
  *grade2 = temp;
}

void bsort2( long int id[], int grade[],int n)
{
  int last, k, i, kk;

  printf("Sorting\n");
  last = n - 1;
  do {
    k = 0;
    for (i = 1; i <= last; i++) {
      if (id[i - 1] > id[i]) {
 id_swap(&id[i - 1], &id[i]);
 grade_swap(&grade[i - 1], &grade[i]);
        k = i;
      }
    }
    last = k;
  } while (k != 0);
}

int binary(long int id[], long int key,int n)
{
  int a, b, middle;
  a = 0;
  b = n;
  do{
     middle = (a+b)/2;
     if( id[middle] < key )
        a = middle+1;
     else if( id[middle] > key)
        b = middle-1;
     else
        return(middle);
   }while( a<=b );

  /* If program reaches this point, no match was found, and the value
     returned will indicate this. */
  return(-1);
}

main()
{
  /*  Declaration Statements  */
  long int id[MAXSTUDENTS], key;
  int i, n, flag, cont, yes_no, grade[MAXSTUDENTS];

  do
  {
     printf("How many students? ( <%4d)",MAXSTUDENTS);
     scanf("%d",&n);
     }while( n>MAXSTUDENTS );

  printf("Enter students' names and ID #'s\n");
  printf("in this format ->ID:9421234[ENTER] (no spaces)\n");
  printf("               ->Grade:49[ENTER]\n");
  for( i=0; i<n; i++){
     printf("Student #%d:\n",i+1);
     printf("ID #:");
     scanf("%ld",&id[i]);
     printf("Grade:");
     scanf("%d",&grade[i]);
     }

  printf("\n\n\nDemonstration of binary search\n\n");

 /* Binary searches only work on sorted lists.  First, we'll sort
    by id number using the improved bubble sort */

  bsort2( id, grade, n );

 do{   /* Keep on looking up names until user wants to quit */

  printf("Enter search key\n");
  scanf("%ld",&key);

  printf("\n  **SEARCHING**\n");

  flag = binary(id, key, n);

 /* flag will equal -1 if no match was found, or the correct
    array subscript for the student */

  cont = 0;
  if(flag == -1){
    printf("Search key not found - check spelling\n");
    printf("Try again (1 for yes/0 for no)? ");
    scanf("%d",&yes_no);
    }
  else {
    printf("  **FOUND**\n");
    printf("ID#:%ld  Grade:%d\n\n",id[flag], grade[flag]);
    printf("Look up another student (1 for yes/0 for no)? ");
    scanf("%d",&yes_no);
    }
 }while(yes_no == 1);

}
/* End of program BINARY */