In this part of the lab, you will create a search function (binary Search L) tha

ID: 3800406 • Letter: I

Question

In this part of the lab, you will create a search function (binary Search L) that is similar to exercise 3 with the following change: You will implement the binary search algorithm using a loop instead of a recursive function. This time all you need to do is to call a search function you create with 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) Return: -1 if the key was not found index of the (first) element where you found the key. Your program should behave the same way as searchArrayl.cpp in the previous exercise; therefore, you may reuse the main function in searchArrayl.cpp Before writing your binary Search L 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

Please find Source Code :- http://pastebin.com/6ZdNXSP4

In iterative solution you will have to keep a left and right indeces;

left = 0;

right = ArraySize - 1;

While left <= right:

Now start finding if the mid of left and right is equal to the word to be searched or not.

if word at middle is equal to the searchWord -> return mid index;

else if the word < searchWord -> You have to search to the right of mid -> left = mid + 1;

else -> You have to search on left of mid -> right = mid - 1;

If you get out of the loop without searchWord being found, it means it does not exist in array of words.

I am also Adding Source Code Below :-

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int binarySearchL(string words[], int n, string word)
{
   sort(words, words + n);
   int left = 0;
   int right = n-1;
   int mid;
   while(left <= right)
   {
       mid = (left + right) / 2;
if (words[mid] == word)
   return mid;
else if (words[mid] > word)
right = mid - 1;
else
left = mid + 1;
   }

return -1;
}

int main()
{
string words[] = {"apple", "cat", "dog", "flag", "gun", "horse", "monkey"};
cout<<binarySearchL(words, 7 , "cat");

return 0;

}

Navigate

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

In this part of the lab, you will write a program that uses a different implemen

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 search function (binary Search L) tha

Question

Explanation / Answer

Related Questions

Navigate