$3\mathrm{.}2\mathrm{.}1$: Recursive algorithm: Search

String target$\_$item and a list of alphabetically sorted strings are read from input. Complete the find$\_$middle$()$ function:

If target$\_$item is alphabetically before mid$\_$value $($the element at index mid$\_$index of the list$),$ output 'Search lower half' and recursively call find$\_$middle$()$ to find target$\_$item in the lower half of the range.

Otherwise, output 'Search upper ha

def find$\_$middle$($search$\_$list, target$\_$item, start$\_$index, end$\_$index$)$:

range$\_$size $=($end$\_$index $-$ start$\_$index$)+1$

mid$\_$index $=($start$\_$index $+$ end$\_$index$)//2$

mid$\_$value $=$ search$\_$list$[$mid$\_$index$]$

if target$\_$item $==$ mid$\_$value:

print$($f$\text{'}\{$target$\_$item$\}$ is found at index $\{$mid$\_$index$\}\text{'})$

elif range$\_$size $==1$:

print$($f$\text{'}\{$target$\_$item$\}$ is not in the list'$)$

else:

$\text{'}\text{'}\text{'}$ Your code goes here $\text{'}\text{'}\text{'}$

target$\_$item $=$ input$()$

data$\_$list $=$ input$().$split$()$

find$\_$middle$($data$\_$list, target$\_$item, $0,$ len$($data$\_$list$)-1)$