String targetItem and integer numData are read from input. Then, numData alphabetically sorted strings are read from input and each string is added to an ArrayList. Complete the findMiddle$()$ method:

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

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

End each output with a newline.

Click here for example

Ex: If the input is:

DMA

$3$

CHE COM DMA

then the output is:

Search upper half

DMA is found at index $2$