Part 1 - Modify the BinarySearch.cpp file to implement the required function for
ID: 3542877 • Letter: P
Question
Part 1 - Modify the BinarySearch.cpp file to implement the required function for a binary search
algorithm. Once the function has been implemented, the program returns the index location of the item in
the array if it is found; otherwise a -1 will be returned. Remember that arrays in C++ are zero-based, so
the first position has an index of 0.
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int binarySearch(string list[], int length, string item);
int main(int argc, char **argv)
{
string stars[] = {
"Adhafera", "Al Athfar", "Al Gieba", "Aladfar", "Almeisan", "Alterf",
"Coxa", "Denebola", "Mebsuta", "Mekbuda", "Pollux", "Propus",
"Ras Elased", "Rasalas", "Sheliak", "Sulafat", "Tejat", "Tsze Tseang",
"Wasat", "Zozma"
};
int numberOfStars = 20;
string item;
int found = -1;
// Call binarySearch to find an item in the array
item = "Pollux";
found = binarySearch(stars, numberOfStars, item);
cout << item << " is at index " << found << endl;
item = "Sol";
found = binarySearch(stars, numberOfStars, item);
cout << item << " is at index " << found << endl;
item = "Sulafat";
found = binarySearch(stars, numberOfStars, item);
cout << item << " is at index " << found << endl;
cout << " ** Press any key to continue ** ";
getchar();
return 0;
}
int binarySearch(string list[], int length, string item)
{
// TODO: Implement the details of the binary search function. Be sure
// to read the textbook chapter before working on this problem. The
// funciton will return -1 if the item is not found in the array.
return -1;
}
Part 2 -
Suppose the declaration for the stars array in Problem 2(a) was as follows:
string stars[] = {
"Sheliak", "Sulafat", "Aladfar", "Al Athfar", "Denebola", "Al Gieba",
"Zozma", "Ras Elased", "Adhafera", "Coxa", "Tsze Tseang", "Alterf",
"Rasalas", "Pollux", "Almeisan", "Wasat", "Mebsuta", "Mekbuda",
"Propus", "Tejat"
};
Briefly explain whether or not this would cause a problem for our binarySearch() function
Explanation / Answer
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int binarySearch(string list[], int length, string item);
int main(int argc, char **argv)
{
string stars[] = {
"Adhafera", "Al Athfar", "Al Gieba", "Aladfar", "Almeisan", "Alterf",
"Coxa", "Denebola", "Mebsuta", "Mekbuda", "Pollux", "Propus",
"Ras Elased", "Rasalas", "Sheliak", "Sulafat", "Tejat", "Tsze Tseang",
"Wasat", "Zozma"
};
int numberOfStars = 20;
string item;
int found = -1;
// Call binarySearch to find an item in the array
item = "Pollux";
found = binarySearch(stars, numberOfStars, item);
cout << item << " is at index " << found << endl;
item = "Sol";
found = binarySearch(stars, numberOfStars, item);
cout << item << " is at index " << found << endl;
item = "Sulafat";
found = binarySearch(stars, numberOfStars, item);
cout << item << " is at index " << found << endl;
cout << " ** Press any key to continue ** ";
getchar();
return 0;
}
int binarySearch(string list[], int length, string item)
{
int first = 0;
int last = length;
while(first<=last)
{
int middle = (first+last)/2;
if(item.compare(list[middle])==0) return middle;
else if(item.compare(list[middle])<0)
last = middle-1;
else
first = middle+1;
}
// TODO: Implement the details of the binary search function. Be sure
// to read the textbook chapter before working on this problem. The
// funciton will return -1 if the item is not found in the array.
return -1;
}