In this part of the lab, you will create a recursive function that searches for

Question

In this part of the lab, you will create a recursive function that searches for a key in an array with a binary search algorithm. Revisit lecture# 6 for the concept of the binary search algorithm. All you need to do is to repeat splitting an array by half and compare the key to the value of the middle element. In main program: Input an array from a file. Call function (check Array Sort) to check if the array is sorted. So far, you can use the code you created from the previous exercises. Exit program if the array is not sorted (assume ascending order), or continue if it is. Therefore, you can use the code that you built so far (exercise 2), and continue to the next steps if the array is sorted. Prompt the user to input search key (k). Call function (binary Search R) to search for the key recursively. Output your search result: "Found key k at index i!" if the key was found. "The key k was not found in the array!" if the key was not found. Your binary Search R function will return an integer value i as the index of the array A where the key is found (or -1 in key is not found), and it will take the following arguments: a string array A (again, it is a pointer) 2 integer values first and last to represent the beginning and ending element positions of A to be searched, the key to search for (a string) Before writing your binary Search R function, think about the algorithm and write it in pseudocode using a piece of paper or a text editor. You need to turn in the pseudocode to receive full credit.

Explanation / Answer

Here is the code for you:

#include <iostream>
#include <fstream>
using namespace std;
/*void BubbleSort(int Array[50], int count)
{
int temp;
for(int i = 0; i < count-1; i++)
for(int j = 0; j < count-i-1; j++)
if(Array[j] > Array[j+1])
{
temp = Array[j];
Array[j] = Array[j+1];
Array[j+1] = temp;
}
}*/
int BinarySearch(int Array[], int low, int high, int key)
{
if(low <= high)
{
int mid = (low+high)/2;
if(Array[mid] == key)
return mid;
else if(key < Array[mid])
return BinarySearch(Array, low, mid-1, key);
else
return BinarySearch(Array, mid+1, high, key);
}
return -1;
}
int main()
{
int Array[50];
cout<<"Enter the name of the file: ";   //Read the file name.
string fileName;
cin>>fileName;
ifstream ipFile;
ipFile.open(fileName);           //Opens the file for input stream.
int count = 0;
while(!ipFile.eof())               //While the file is not empty.
ipFile>>Array[count++];           //Read the elements into the integer array.
  
//BubbleSort(Array, count);           //Sort the array, so that we can implement the Binary Search.
  
cout<<"Enter the key to search for: ";   //Read the key to search for.
int key;
cin>>key;
int pos = BinarySearch(Array, 0, count-1, key);   //Call the Binary search.
if(pos == -1)
cout<<"Number is not available."<<endl;
else
cout<<"Number found at position: "<<pos<<endl;
//And to print all the positions:
/*cout<<"Number also found at positions: ";
while(Array[pos--] == key);
pos += 2;
while(Array[pos++] == key)
cout<<pos<<" ";
cout<<endl; */
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.