Code:
/* Name Search
This program frst sorts the array and then demonstrates
the binarySearch function, which performs a binary search on an integer array
to find the name by comparing strings.
*/
#include <iostream>
#include <cstring> //for use with c strings
using namespace std;
// Function prototype
int binarySearch(char[20][17], int, char[1][17]); //searching function
void sort(char[20][17], int); //sorting function
int main()
{
const int NUM_NAMES = 20, SIZE = 17;
int results; //value returned if name faund or not
char name[1][SIZE]; //name string for input by user
char names[NUM_NAMES][SIZE] = {"Collins, Bill", "Smith, Bart", "Allen, Jim",
"Griffin, Jim", "Stamey, Marty", "Rose, Geri",
"Taylor, Terri", "Johnson, Jill", "Allison, Jeff",
"Looney, Joe", "Wolfe, Bill", "James, Jean",
"Weaver, Jim", "Pore, Bob", "Rutherford, Greg",
"Javens, Renee", "Harrison, Rose", "Setzer, Cathy",
"Pike, Gordon", "Holland, Beth" };
cout <<"Enter the name to search: ";
cin.getline(name[0], SIZE); //line input which count spaces as well
sort(names, NUM_NAMES); //calling function to sort the array in alphabetical order
results = binarySearch(names, NUM_NAMES, name); //calling function to search for name
if (results == -1){
cout << "The name does not exist in the array.\n";
}
else{
cout << "The name is found at element " << results;
cout << " in the array.\n";
}
return 0;
}
//Definition of function sort
//This function is a selection sort function, which performs
//an ascending order selection sort on array.
//Perimeter size is the number of element in the array, with NUM_NAMES
//as a argument.
void sort(char array1[20][17], int size){
int start, minIndex;
char minValue[17]; //stores the minimum value with each loop iteration
for(start = 0; start < (size - 1); start++){
minIndex = start;
strcpy(minValue, array1[start]); //strcpy coppies strings
for(int i = start + 1; i < size; i++){ //the inner for loop searches for the name with the
if(strcmp(array1[i], minValue) < 0){ //lowest alphabetical order, strcmp checks for alphabetical position
strcpy(minValue, array1[i]);
minIndex = i;
}
}
strcpy(array1[minIndex], array1[start]);
strcpy(array1[start], minValue);
}
}
// Definition of binarySearch function
// The binarySearch function performs a binary search on an
// integer array. array, which has a maximum of NUM_NAMES
// elements, is searched for the name stored in char name. If the
// number is found, its array subscript is returned. Otherwise,
// -1 is returned indicating the value was not in the array.
int binarySearch(char array1[20][17], int size, char name[1][17]){
int first = 0, // First array element
last = size - 1, // Last array element
middle, // Mid point of search
position = -1; // Position of search value
bool found = false; // Flag
while (!found && first <= last){
middle = (first + last) / 2; // Calculate mid point
if (strcmp(array1[middle], name[0]) == 0){ // If value is found at mid
found = true;
position = middle;
}
else if(strcmp(name[0], array1[middle]) < 0){ // If value is in lower half
last = middle - 1;
}
else{
first = middle + 1; // If value is in upper half
}
}
return position; //the position of the name searched in the array
}
.
Originally Posted by Adak
