Binary Search Help

Pages: 12
im trying to do a binary search of of a student names. When it does the binary search it asks for the student name as search key: enter name here, and then it shows the test score for that person. Then it asks for another search.
I cannot figure it out. Some help would be nice.
#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;

void getData(int size, int [], char [][6]);
void sortData(char [][6], int[], int);
void printData(char [][6], int[]);
int searchData(char [][6], int[], int);

void main(){
int scores[5];
char students[5][6];
int size;

cout << "Enter size for arrays: ";
cin >> size;
getData(size,scores,students);
printData(students,scores);
sortData(students, scores, 5);





}

void getData(int size, int testScore[],char studentName[][6]) {

int index;

for (index = 0; index <= size -1; index++){
cout << "Enter " <<(index +1) << "th student name: "
<< ": ";
cin >> studentName[index];
cout << "Enter test score for " << studentName[index]
<< ": ";
cin >> testScore[index];

while (0 > testScore[index] || testScore[index] > 100){
cout << "Re-enter test score for " << studentName[index]
<< ": ";
cin >> testScore[index];

}// end while
}// end for

}

void sortData(char studentName[][6],int testScore[],int size){
bool swap;
char temp[6];

do {
swap = false;
for (int count = 0; count < (size - 1); count++) {
if (strcmp(studentName[count], studentName[count+1]) > 0) {
strcpy_s(temp,6, studentName[count]);
strcpy_s(studentName[count],6, studentName[count+1]);
strcpy_s(studentName[count+1],6, temp);
swap = true;
} // end if
} // end for
} while (swap);


}

void printData(char studentName[][6], int testScores[]){

cout << "ARRAYS BEFORE SORTING" << endl;
cout << "NAME" << "\t\t" << "SCORE" << endl;
for (int i = 0; i < 5; i++)
cout << studentName[i] << "\t\t" << static_cast<int>(testScores[i]) << endl;

sortData(studentName, testScores, 5);

cout << "ARRAYS AFTER SORTING :" << endl;
cout << "NAME" << "\t\t" << "SCORE" << endl;
for (int i = 0; i < 5; i++)
cout << studentName[i] << "\t\t" << static_cast<int>(testScores[i]) << endl;

int ok;
cin >> ok;

}
int searchData(char studentName[][6], char key[], int size){
int first, last, mid;
bool found = false;
int position = -1;

first = 0;
last = size - 1;

while (first <= last && ! found) {
mid = (first + last) / 2;

if (strcmp(studentName[mid], key) == 0) {
position = mid;
found = true;
}
else if (strcmp(studentName[mid],key) > 0)
last = mid - 1;
else
first = mid + 1;
// end if
} // end while
return position;
} // end binarySearch
void getData(int size, int [], char [][6]);
void sortData(char [][6], int[], int);
void printData(char [][6], int[]);
int searchData(char [][6], int, int[]);

void main(){
int scores[5];
char students[5][6];
char key[10];
char answer[4] = "yes";
int size;
int index;


cout << "Enter size for arrays: ";
cin >> size;
getData(size,scores,students);
printData(students,scores);
sortData(students, scores, 5);



while (strcmp(answer, "yes") == 0) {
cout << "Enter a student name as search key: ";
cin >> students;
index = searchData (students, size, scores);
if (index == -1)
cout << "Not found." << endl;
else
cout << "Test score for " << students << "is " << key;
// end if
cout << "Another search? yes/no: ";
cin >> answer;
} // end while
}

}
int searchData(char studentName[][6], int size, int testScores[]){
int first, last, mid;
bool found = false;
int position = -1;

first = 0;
last = size - 1;

while (first <= last && ! found) {
mid = (first + last) / 2;

if (strcmp(studentName[mid], testScores ) == 0) {
position = mid;
found = true;
}
else if (strcmp(studentName[mid], testScores) > 0)
last = mid - 1;
else
first = mid + 1;
// end if
} // end while
return position;
} // end binarySearch

i got this but its still wrong. i have no idea what to fix. please help me
Please put code tags [code] [/code] around your code. It makes it much easier to read your code because it keeps the formatting intact.
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;

void getData(int size, int [], char [][6]);
void sortData(char [][6], int[], int);
void printData(char [][6], int[]);
int searchData(char [][6], int, int[], char []);

void main(){
	int scores[5];
	char students[5][6];
	char key[6];
	char answer[4] = "yes";
	int size;
	int index;
	
	
	cout << "Enter size for arrays: ";
	cin >> size;
	getData(size,scores,students);
	printData(students,scores);
	sortData(students, scores, 5);


	
	while (strcmp(answer, "yes") == 0) {
		cout << "Enter a student name as search key: ";
		cin >> key;
		index = searchData(students, size, scores, key);
		if (index == -1)
			cout << "Not found." << endl;
		else
			cout << "Test score for "<< students << "is " << index + 1 << endl;
		// end if
		cout << "Do you want another search? yes/no: ";
		cin >> answer;
	} // end while
	

}

	
	
	
	



void getData(int size, int testScore[],char studentName[][6]) {

	int index;
	
	for (index = 0; index <= size -1; index++){
		cout << "Enter " <<(index +1) << "th student name: "
			 << ": ";
		cin >> studentName[index];
		cout << "Enter test score for " << studentName[index] 
			 << ": ";
		cin >> testScore[index];

			while (0 > testScore[index] || testScore[index] > 100){
				cout << "Re-enter test score for " << studentName[index]
					 << ": ";
				cin >> testScore[index];
		
			}// end while
	}// end for
	
}

void sortData(char studentName[][6],int testScore[],int size){
	bool swap;
	char temp[6];
	
	do {
		swap = false;
		for (int count = 0; count < (size - 1); count++) {
			if (strcmp(studentName[count], studentName[count+1]) > 0) {
				strcpy_s(temp,6, studentName[count]);
				strcpy_s(studentName[count],6, studentName[count+1]);
				strcpy_s(studentName[count+1],6, temp);
				swap = true;
			} // end if
		} // end for
	} while (swap);
	

}

void printData(char studentName[][6], int testScores[]){

	cout << "ARRAYS BEFORE SORTING" << endl;
	cout << "NAME" << "\t\t" << "SCORE" << endl;
	for (int i = 0; i < 5; i++)
		cout << studentName[i] << "\t\t" << static_cast<int>(testScores[i]) << endl;

	sortData(studentName, testScores, 5);

	cout << "ARRAYS AFTER SORTING :" << endl;
	cout << "NAME" << "\t\t" << "SCORE" << endl;
	for (int i = 0; i < 5; i++)
		cout << studentName[i] <<  "\t\t" << static_cast<int>(testScores[i]) << endl;

	int ok;
	cin >> ok;

}
int searchData(char studentName[][6], int size, int testScores[], char *key){
	int first, last, mid;
	bool found = false;
	int position = -1;
	
	first = 0;
	last = size - 1;

	while (first <= last && ! found) {
		mid = (first + last) / 2;

		if (strcmp(studentName[mid], key ) == 0) {
			position = mid;
			found = true;
		}
		else if (strcpy(studentName[mid], key) > 0)
			last = mid - 1;
		else
			first = mid + 1;
		// end if
	} // end while
	return position;
} 
idk where to go from there. plz help
plzzzzzzzzzzz help me
What is the problem with your program? What does it not do? You can't expect us to read all of it, searching for your error.
i need to do this.
make A function named searchData that uses binary search to search the studentName array for a supplied search key value (i.e., a student name) and returns -1 if the search is unsuccessful, and the index of the found element if the search is successful. The function main should prompt the user to enter a search key (a student name value), call the function searchData, and print the result of the search (i.e., the test score of the student whose name is supplied as the search key) in a loop that executes as long as the user want to repeat the search.

i cant get it to show this:
Enter a student name as search key: person's name
test score for person's name: Score
another search? yes/no: yes or no
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void getData(int size, int [], char [][6]);
void sortData(char [][6], int[], int);
void printData(char [][6], int[]);
int searchData(char [][6], int, char[]);

void main(){
	int scores[5];
	char students[5][6];
	char key[6];
	char answer[4] = "yes";
	int size;
	int index;
	
	
	cout << "Enter size for arrays: ";
	cin >> size;
	getData(size,scores,students);
	printData(students,scores);
	sortData(students, scores, 5);

	while (strcmp(answer, "yes") == 0) {
		cout << "Enter a student name as search key: ";
		cin >> key;
		index = searchData(students, size, key);
		if (index == -1)
			cout << "Not found." << endl;
		else
			cout << "Test score for "<< students << "is " << index + 1 << endl;
		// end if
		cout << "Do you want another search? yes/no: ";
		cin >> answer;
	} // end while
int searchData(char studentName[][6], int size, char searchKey[]){
	int first, last, mid;
	bool found = false;
	int position = -1;
	
	first = 0;
	last = size - 1;

	while (first <= last && ! found) {
		mid = (first + last) / 2;

		if (strcmp(studentName[mid], searchKey) == 0) {
			position = mid;
			found = true;
		}
		else if (strcmp(studentName[mid], searchKey) > 0)
			last = mid - 1;
		else
			first = mid + 1;
		// end if
	} // end while
	return position;
} // end binarySearch 
Last edited on
I still can't understand what you want help with. You posted what seemed to be a full solution on your first post. That doesn't work? What part doesn't work?
what i had first doesnt work. just forget about it.
In this one i cant get it to show this
[code]
cout << "Enter a student name as search key: ";
cin >> key;
[\code]

once i enter the names and their test score. it sorts and prints them. then it doesnt go to the next thing which should be "Enter a student name as search key: "
but it doesnt show it
Does it display "Do you want another search"? Does the program ends after that (you didn't post your full main function)?
this is my whole main funtion
void main(){
int scores[5];
char students[5][6];
char key[6];
char answer[4] = "yes";
int size;
int index;


cout << "Enter size for arrays: ";
cin >> size;
getData(size,scores,students);
printData(students,scores);
sortData(students, scores, 5);

while (strcmp(answer, "yes") == 0) {
cout << "Enter a student name as search key: ";
cin >> key;
index = searchData(students, size, key);
if (index == -1)
cout << "Not found." << endl;
else
cout << "Test score for "<< students << "is " << index + 1 << endl;
// end if
cout << "Do you want another search? yes/no: ";
cin >> answer;
} // end while
}

it stops at sortData(students, scores, 5);
Does your program return from sortData()? Print something between it and the while loop to discover.

Also, a better way to do your while loop is

1
2
3
4
5
6
7
char answer[4];

do
{
	// code
	cin >> answer;
} while(strcmp(answer, "yes") == 0);
here is my sortData
void sortData(char studentName[][6],int testScore[],int size){
bool swap;
char temp[6];

do {
swap = false;
for (int count = 0; count < (size - 1); count++) {
if (strcmp(studentName[count], studentName[count+1]) > 0) {
strcpy_s(temp,6, studentName[count]);
strcpy_s(studentName[count],6, studentName[count+1]);
strcpy_s(studentName[count+1],6, temp);
swap = true;
} // end if
} // end for
} while (swap);

}


i just figured out it only sorts the names. it doesnt sort the the testScores with the names. idk how to fix that
can u like call me or something. it would be soo much easier. 9372322493
Sorry, not in the US (if that's where you're at, but probably not there either). Did you check if it ever returns?

1
2
sortData(students, score, 5);
cout << "returned from sortData\n";
the sortData shows up when i run it. after that nothing
like there is nothing after that
OK, in your print data you have this

1
2
int ok;
cin >> ok;

If you remove that, it works. You probably want something like a "press enter to continue". Don't do it like that. Read this:

http://www.cplusplus.com/forum/beginner/1988/
Pages: 12