String stateMatch 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 findMatch$()$ method:

If stateMatch is alphabetically before middleValue $($the element at index middleIndex of the ArrayList$),$ output "Search lower half" and recursively call findMatch$()$ to find stateMatch in the lower half of the range.

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

End each output with a newline.

import java.util.Scanner;

import java.util.ArrayList;

public class FindState $\{$

public static void findMatch$($ArrayList searchList, String stateMatch, int minIndex, int maxIndex$)\{$

int rangeSize;

int middleIndex;

String middleValue;

rangeSize $=($maxIndex $-$ minIndex$)+1$;

middleIndex $=($minIndex $+$ maxIndex$)/2$;

middleValue $=$ searchList.get$($middleIndex$)$;

if $($stateMatch$.$equals$($middleValue$))\{$

System.out.println$($stateMatch $+"$ is found at index $"+$ middleIndex$)$;

$\}$

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

System.out.println$($stateMatch $+"$ is not in the list"$)$;

$\}$

else $\{$

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

$\}$

$\}$

public static void main$($String$[]$ args$)\{$

Scanner scnr $=$ new Scanner$($System$.$in$)$;

ArrayList dataList $=$ new ArrayList$()$;

String stateMatch;

int numData;

int i;

stateMatch $=$ scnr$.$next$()$;

numData $=$ scnr$.$nextInt$()$;

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

dataList.add$($scnr$.$next$())$;

$\}$

findMatch$($dataList$,$ stateMatch, $0,$ dataList.size$()-1)$;

$\}$

$\}$