String matchItem and integer numData are read from input. Then, numData alphabetically sorted strings are read from input and each string is appended to a vector. Complete the Find$()$ function:

If matchItem is alphabetically before midValue $($the element at index midIndex of the vector$),$ output "Search lower half" and recursively call Find$()$ to find matchItem in the lower half of the range.

Otherwise, output "Search upper half" and recursively call Find$()$ to find matchItem in the upper half of the range.

End each output with a newline. #include

#include

#include

using namespace std;

void Find$($vector allNames, string matchItem, int startIndex, int endIndex$)\{$

int midIndex;

int rangeSize;

string midValue;

rangeSize $=($endIndex $-$ startIndex$)+1$;

midIndex $=($startIndex $+$ endIndex$)/2$;

midValue $=$ allNames.at$($midIndex$)$;

if $($matchItem $==$ midValue$)\{$

cout $<<$ matchItem $<<"$ is found at index $"<<$ midIndex $<<$ endl;

$\}$

else if $($rangeSize $==1)\{$

cout $<<$ matchItem $<<"$ is not in the list" $<<$ endl;

$\}$

else $\{$

$/*$ Your code goes here $*/$

$\}$

$\}$

int main$()\{$

string matchItem;

vector dataList;

int numData;

int i;

string item;

cin $>>$ matchItem;

cin $>>$ numData;

for $($i $=0$; i $<$ numData; $++$i$)\{$

cin $>>$ item;

dataList.push$\_$back$($item$)$;

$\}$

Find$($dataList$,$ matchItem, $0,$ dataList.size$()-1)$;

return $0$;

$\}$