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

ID: 3673666 • Letter: I

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# 4 for the concept of the binary search algorithm. All you need to do is to repeat spitting 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 (checkArraySort) 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, 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 (fc). Call function (binarySearchR) 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 round In me array!" if the key was not found. Your binarySearchR 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) the number of elements in the array the key to search for (a string) Before writing your binarySearchR 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

#include <bits/stdc++.h>
using namespace std;

bool checkArraySort(int a[], int len) {
   for (int i = 0; i < len - 1; ++i) {
       if (a[i] > a[i + 1]) return false;
   }
   return true;
}

int binarySearch(int a[], int lo, int hi, int key) {
   if (lo > hi) {
       return -1;
   }
   if (lo == hi) {
       if (a[lo] == key) return lo;
       else return -1;
   }
   int mid = (lo + hi) / 2;
   if (a[mid] == key) return mid;
   else if (a[mid] < key) return binarySearch(a, mid + 1, hi, key);
   else return binarySearch(a, lo, mid - 1, key);
}

int main() {
ifstream f("input.txt");

   // take input number of elements in array
   int n;
   f >> n;

// initialize array
int *a = new int[n];

   // take input array elements
   for (int i = 0; i < n; ++i) {
       f >> a[i];
   }

   // check if array is sorted
   if (checkArraySort(a, n)) {
       int key;
       cout << "Enter key to search: ";
       cin >> key;

       // get the index of key if it is there
       int index = binarySearch(a, 0, n - 1, key);
       if (index == -1) {
           cout << "The key " << key << " was not found in the array! ";
       } else {
           cout << "Found key " << key << " at index " << index << "! ";
       }
   } else {
       cout << "Array is not sorted, exiting the program." << endl;
   }

f.close();

return 0;
}

Navigate

In this part of the lab, you will create a function check Array Sort that checks

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

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

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

Question

Explanation / Answer

Related Questions

Navigate