#define SIZE 10 #include <iostream> using namespace std; char list[SIZE] = {\'A\
ID: 658671 • Letter: #
Question
#define SIZE 10 #include <iostream> using namespace std; char list[SIZE] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'}; // recursively search the array list for key // return the index to list if key is found. else return -1 // If required you can create indirect recursive function int recBinarySearch(char key) { //TODO: your implementation } int rotatedList[SIZE] = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7} int recBinarySearchOnRotatedData(int key) { // TODO : your implementation } int main() { cout << "Binary Search on sorted data"<<endl; cout << "searching B: " << recBinarySearch('B') << endl; cout << "searching E: " << recBinarySearch('E') << endl; cout << "searching J: " << recBinarySearch('J') << endl; cout << "searching A: " << recBinarySearch('A') << endl; cout << "searching Z: " << recBinarySearch('Z') << endl; cout << "Binary Search on sorted data"<<endl; cout << "searching 8: " << recBinarySearchOnRotatedData(8) << endl; cout << "searching 10: " << recBinarySearchOnRotatedData(10) << endl; cout << "searching 7: " << recBinarySearchOnRotatedData(7) << endl; cout << "searching 3: " << recBinarySearchOnRotatedData(3) << endl; cout << "searching 0: " << recBinarySearchOnRotatedData(0) << endl; return 0; }
Explanation / Answer
The completed code is given below:-
#define SIZE 10
#include <iostream>
using namespace std;
char list[SIZE] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
int binarySearchList(char,int,int);
int binarySearchRotatedData(int,int,int);
void sortArray();
// recursively search the array list for key
// return the index to list if key is found. else return -1
// If required you can create indirect recursive function
int recBinarySearch(char key)
{
//TODO: your implementation
return binarySearchList(key,0,SIZE-1);
}
int binarySearchList(char key,int lower,int upper){
int mid;
if(lower<=upper){
mid=(lower+upper)/2; //find the present middle position of the array
if(key==list[mid]){ //if search key is equal to present middle element of list
return mid; //return the list index where the search key is found
}
else if(key<list[mid]){
return binarySearchList(key,lower,mid-1); //recursively call binarySearchList() method
}
else
return binarySearchList(key,mid+1,upper); //recursively call binarySearchList() method
}
else
return -1; //if search key is not found return -1
}
int rotatedList[SIZE] = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7};
void sortArray(){ //sort array in ascending order
int temp;
for(int i=0;i<SIZE-1;i++){
for(int j=0;j<SIZE-i-1;j++){
if(rotatedList[j]>rotatedList[j+1]){
temp=rotatedList[j];
rotatedList[j]=rotatedList[j+1];
rotatedList[j+1]=temp;
}
}
}
}
int recBinarySearchOnRotatedData(int key)
{
// TODO : your implementation
return binarySearchRotatedData(key,0,SIZE-1);
}
int binarySearchRotatedData(int key,int lower,int upper){ //method to search for data on rotatedList
int mid;
if(lower<=upper){
mid=(lower+upper)/2; //find the present middle position of the array
if(key==rotatedList[mid]){ //if search key is equal to present middle element of rotated list
return mid; //return the list index where the search key is found
}
else if(key<rotatedList[mid]){
return binarySearchRotatedData(key,lower,mid-1); //recursively call binarySearchRotatedData method
}
else
return binarySearchRotatedData(key,mid+1,upper); //recursively call binarySearchRotatedData method
}
else
return -1; //if search key is not found return -1
}
int main()
{
cout << "Binary Search on sorted data"<<endl;
cout << "searching B: " << recBinarySearch('B') << endl;
cout << "searching E: " << recBinarySearch('E') << endl;
cout << "searching J: " << recBinarySearch('J') << endl;
cout << "searching A: " << recBinarySearch('A') << endl;
cout << "searching Z: " << recBinarySearch('Z') << endl;
sortArray(); //sort the rotatedList before performing binary search on it
cout<<" Sorted rotatedList: ";
for(int i=0;i<SIZE;i++){ //display the sorted rotatedList
cout<<rotatedList[i]<<" ";
}
cout<" ";
cout << "Binary Search on sorted data"<<endl;
cout << "searching 8: " << recBinarySearchOnRotatedData(8) << endl;
cout << "searching 10: " << recBinarySearchOnRotatedData(10) << endl;
cout << "searching 7: " << recBinarySearchOnRotatedData(7) << endl;
cout << "searching 3: " << recBinarySearchOnRotatedData(3) << endl;
cout << "searching 0: " << recBinarySearchOnRotatedData(0) << endl;
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.