1. You are going to implement a binary search function that returns an index of
ID: 3594515 • Letter: 1
Question
1. You are going to implement a binary search function that returns an index of the Employee data with the value that you are searching for; otherwise, returns -1 if the Employee data does not exist.
2. You are also going to implement an exhaustive search function that returns an index of the Employee data with the value that you are searching for; otherwise, returns -1 if the Employee data does not exist.
Main program:
1. Read from a file dataset of 10 employee records containing their first name, last name, age, and salary sorted by first name in ascending order and create an array of Employee structure.
2. Search for first name “Sam” using binary search and record the execution time for this function. Print out the corresponding employee record and the time it took on the console.
3. Now, search for first name “Sam” using exhaustive search and record the execution time for this function. Print out the corresponding employee record and the time it took on the console.
4. Search for first name “Yuyan” using binary search and record the execution time for this function. Print out the corresponding employee record and the time it took on the console.
5. Now, search for first name “Yuyan” using exhaustive search and record the execution time for this function. Print out the corresponding employee record and the time it took on the console.
6. Use printf to explain the time difference between binary and exhaustive search on the console for two different scenarios.
this is the typedef
typedef struct employee{
char fname[25], lname[25]; //first name and last name of an employee
int age;
int salary;
}Employee;
dataset is listed below
Sam,May,19,685
Samuel,Morrison,47,9565
Zachary,Schultz,60,7157
Virgie,Norris,45,3822
Franklin,Cohen,64,6383
Etta,Estrada,34,5612
Bertie,Gutierrez,30,145
Donald,Pearson,36,2164
Abbie,Park,22,3507
Roy,Salazar,55,22
Explanation / Answer
Given below is the program to time the searches. In order that binary search be performed, the data should be sorted. So after loading from file, the array is first sorted.
Please don't forget to rate the answer if it helped. Thank you
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
typedef struct employee{
char fname[25], lname[25]; //first name and last name of an employee
int age;
int salary;
}Employee;
void binarySearch(Employee emps[], int n, char *fname);
void exhaustiveSearch(Employee emps[], int n, char *fname);
void readFile(FILE *fp, Employee emps[]);
void sort(Employee emps[], int n);
int main()
{
FILE *fp;
char filename[30];
Employee emps[10];
printf("Enter input filename: ");
scanf("%s", filename);
fp = fopen(filename, "r");
if(fp == NULL)
{
printf("Error opening input file %s ",filename);
return 1;
}
printf("reading data from file... ");
readFile(fp, emps);
printf("sorting the records... ");
sort(emps, 10); //sort the array on fname before searching
binarySearch(emps, 10, "Sam");
exhaustiveSearch(emps, 10, "Sam");
binarySearch(emps, 10, "Yuyan");
exhaustiveSearch(emps, 10, "Yuyan");
}
void binarySearch(Employee emps[], int n, char *fname)
{
clock_t start, end;
double cpu_time;
int first = 0, last = n-1;
int mid = 0;
int cmp;
int index;
start = clock();
while(first <= last)
{
mid = (first + last ) / 2;
cmp = strcmp(emps[mid].fname, fname);
if(cmp == 0)
break;
else if(cmp < 0)
first = mid + 1;
else
last = mid -1;
}
if(first > last)
index = -1;
else
index = mid;
end = clock();
cpu_time = ((double) (end - start)) / CLOCKS_PER_SEC;
if(index == -1)
printf("%s NOT found. Binary search took %f secs ", fname, cpu_time);
else
printf("%s found at index %d. Binary search took %f secs ", fname, index, cpu_time);
}
void exhaustiveSearch(Employee emps[], int n, char *fname)
{
clock_t start, end;
double cpu_time;
int index = 0;
start = clock();
for(index = 0; index < n; index++)
{
if(strcmp(emps[index].fname, fname) == 0)
break;
}
end = clock();
cpu_time = ((double) (end - start)) / CLOCKS_PER_SEC;
if(index == n)
printf("%s NOT found. Exhaustive search took %f secs ", fname, cpu_time);
else
printf("%s found at index %d. Exhaustive search took %f secs ", fname, index, cpu_time);
}
void readFile(FILE *fp, Employee emps[])
{
int i;
char str[100];
char *token;
for(i = 0 ;i < 10; i ++) //read 10 employees
{
fgets(str, 100, fp);
//use the delimiter and get the values into struct
token = strtok(str, ",");
strcpy(emps[i].fname, token);
token = strtok(str, ",");
strcpy(emps[i].lname, token);
token = strtok(str, ",");
emps[i].age = atoi(token);
token = strtok(str, " ");
emps[i].salary = atoi(token);
}
fclose(fp);
}
void sort(Employee emps[], int n)
{
int i, j, minIdx;
Employee temp;
for(i = 0; i < n; i++)
{
minIdx = i;
for(j = i +1; j < n; j++)
{
if(strcmp(emps[j].fname, emps[minIdx].fname) < 0)
minIdx = j;
}
if(i != minIdx)
{
temp = emps[i];
emps[i] = emps[minIdx];
emps[minIdx] = temp;
}
}
}
input file: emps.txt
Sam,May,19,685
Samuel,Morrison,47,9565
Zachary,Schultz,60,7157
Virgie,Norris,45,3822
Franklin,Cohen,64,6383
Etta,Estrada,34,5612
Bertie,Gutierrez,30,145
Donald,Pearson,36,2164
Abbie,Park,22,3507
Roy,Salazar,55,22
output
Enter input filename: emps.txt
reading data from file...
sorting the records...
Sam found at index 6. Binary search took 0.000004 secs
Sam found at index 6. Exhaustive search took 0.000002 secs
Yuyan NOT found. Binary search took 0.000001 secs
Yuyan NOT found. Exhaustive search took 0.000000 secs
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.