/*

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 */

/*

Input :

8

9611684 67

9613986 65

9412978 72

9613693 73

9515010 82

9510633 71

9513221 69

0000000 00

Output :

How many students? ( < 50)8

Enter students' names and ID #'s

in this format ->ID:9421234[ENTER] (no spaces)

->Grade:49[ENTER]

Student #1:

ID #:9611684

Grade:67

Student #2:

ID #:9613986

Grade:65

Student #3:

ID #:9412978

Grade:72

Student #4:

ID #:9613693

Grade:73

Student #5:

ID #:9515010

Grade:82

Student #6:

ID #:9510633

Grade:71

Student #7:

ID #:9513221

Grade:69

Student #8:

ID #:0000000

Grade:00

Demonstration of binary search

Sorting

Enter search key

9611684

**SEARCHING**

**FOUND**

ID#:9611684 Grade:67

Look up another student (1 for yes/0 for no)?0

*/