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