Implemement the intervalSearch method in Java. The instructions, UML diagram, skeleton program, and two sample runs are given below.

-------------

IntervalSearch.java

package Lab10; import java.util.Random; import java.util.Scanner; import java.util.TreeSet; // TODO Project 4 /**  * A class for finding an interval in a sorted array that holds everything in a list of the target data values.  *  * Consider an array data of n numerical values in sorted order and a list of numerical target values. Your goal is to  * compute the smallest range of array indices that contains all of the target values.  *  * If a target value is smaller than data[0], the range should start with -1.  * If a target value is larger than data[n - 1], the range should end with n.  *  * For example, given the array: 5 8 10 13 15 20 22 26 and the target values (8, 2, 9, 17), the range is -1 to 5.  *  * Devise and implement an efficient algorithm that solves this problem.  * HINT:  * 1) Find the max target and min target in the list of target values.  * 2) Utilize the iterative binary search algorithm to find the position that min target and max target values  * would have if inserted into the list of sorted data.  *  *  * @author YOUR NAME  * @version 10/30/2018  */  public class IntervalSearch { /* Finds the smallest interval in the sortedData holding all the target values. * @param sortedData a sorted array of comparable values (n >= 1) * @param targetValues a list of comparable values (m >= 1) * @return an ordered pair of integers, where the first value is the largest * index i in the sorted data such that data[i] is smaller than all target values. * If a target value is smaller than data[0], return -1. * The second value in the pair is the smallest index j in the sorted data such that * data[j] is greater than all target values. If a target value is larger than * the last value in data, return the n. */ public static > Interval findInterval(T[] sortedData, TreeSet targetValues) { int leftBoundary = -1; int rightBoundary = sortedData.length; System.out.println("Inside the findInterval method - you need to implement me iteratively"); //System.out.println("Target list is " + targetValues); // STEP 1 - Run the code first before starting the implementation if (sortedData.length > 0 && targetValues.size() > 0) { // YOUR CODE GOES HERE // Implement the method WITHOUT RECURSION // STEP 2 - get the smallest and the largest targets //System.out.println("Smallest target is " + smallestTarget // + "; largest target is " + largestTarget); // STEP 3 - utilizing the binary search algorithm search for the smallest target // DO NOT USE RECURSION //System.out.println("\tLeft: " + left + " Middle: " + mid + " Right: " + right); // STEP 4 - set the left boundary to the appropriate index //System.out.println("\tLeft Boundary set to " + leftBoundary); // STEP 5 - utilizing the binary search algorithm search for the largest target // DO NOT USE RECURSION // NOTE that you can reduce the searches by setting the left index // to the leftBoundary that you calculated in step 4 //System.out.println("\tLeft: " + left + " Middle: " + mid + " Right: " + right); // STEP 6 - set the right boundary to the appropriate index //System.out.println("\tRight Boundary set to " + rightBoundary); } return new Interval(leftBoundary, rightBoundary); } // end findInterval /**  * Initialize the list of ints by reading them from the keyboard  * @return a list of integers  */  public static TreeSet getTargetValues() { TreeSet targets = new TreeSet(); System.out.println("Enter the list of integer values separated by spaces (all on one line), " + "or just press enter if you are done."); Scanner keyboard = new Scanner(System.in); Scanner dataValues = new Scanner(keyboard.nextLine()); while (dataValues.hasNextInt()) { targets.add(dataValues.nextInt()); } return targets; } public static void main(String args[]) { Random generator = new Random(); Scanner keyboard = new Scanner(System.in); System.out.println("How many elements in the array?"); final int DEFAULT = 10; int size; try { size = keyboard.nextInt(); } catch(NumberFormatException e) { System.out.println("Could not convert input to an integer"); System.out.println(e.getMessage()); System.out.println("Will use " + DEFAULT + " as the default value"); size = DEFAULT; } // generate a random array of integers Integer sortedData[] = new Integer[size]; for(int i = 0; i  0 && sortedData[i] out.println("The sorted data is:"); for (int i = 0; i out.print("["+ i + "]=" + sortedData[i] + " "); } System.out.println(); //get the target values TreeSet targets = getTargetValues(); while (targets.size() > 0) { System.out.println("The interval is: " + findInterval(sortedData, targets)); System.out.println(); targets = getTargetValues(); } System.out.println(" *** Done ***"); } } // end SearchArray

------------------

Interval.java

package Lab10; /**  * A class that represents an interval in an array. It is utilized by the IntervalSearch.  *  * @author atb  * @version 10/30/2018  */ public class Interval { private int first, second; public Interval(int firstItem, int secondItem) { this.first = firstItem; this.second = secondItem; } // end constructor public int getFirst() { return this.first; } // end getFirst public int getSecond() { return this.second; } // end getSecond public String toString() { return "(" + this.first + ", " + this.second + ")"; } // end toString } // end Interval

-------------------------

SAMPLE RUN #1

See sample run #1 (no seed):

How many elements in the array?

13

The sorted data is:

[0]=8 [1]=8 [2]=10 [3]=11 [4]=16 [5]=22 [6]=27 [7]=35 [8]=36 [9]=36 [10]=45 [11]=48 [12]=50

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

2 3

Target list is [2, 3]

The interval is: (-1, -1)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

60 70

Target list is [60, 70]

The interval is: (13, 13)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

11 27

Target list is [11, 27]

The interval is: (3, 6)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

15

Target list is [15]

The interval is: (3, 4)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

9 29

Target list is [9, 29]

The interval is: (1, 7)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

3 46

Target list is [3, 46]

The interval is: (-1, 11)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

15 90

Target list is [15, 90]

The interval is: (3, 13)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

*** Done ***

-----------------

SAMPLE Run #2

See sample run #2 (seed set to 7 and added tracing):

How many elements in the array?

17

The sorted data is:

[0]=6 [1]=10 [2]=15 [3]=19 [4]=19 [5]=23 [6]=31 [7]=40 [8]=40 [9]=44 [10]=44 [11]=46 [12]=54 [13]=55 [14]=60 [15]=62 [16]=63

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

44

Target list is [44]

Search on the smallest value

Left Boundary set to 9

Search on the largest value

Left: 9 Middle: 12 Right: 16

Left: 9 Middle: 10 Right: 11

Left: 9 Middle: 10 Right: 11

Right Boundary set to 10

The interval is: (9, 10)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

19

Target list is [19]

Search on the smallest value

Left Boundary set to 3

Search on the largest value

Left: 3 Middle: 9 Right: 16

Left: 3 Middle: 5 Right: 8

Left: 3 Middle: 3 Right: 4

Left: 3 Middle: 3 Right: 4

Right Boundary set to 4

The interval is: (3, 4)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

40

Target list is [40]

Search on the smallest value

Left Boundary set to 7

Search on the largest value

Left: 7 Middle: 11 Right: 16

Left: 7 Middle: 8 Right: 10

Left: 7 Middle: 8 Right: 10

Right Boundary set to 8

The interval is: (7, 8)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

19 44

Target list is [19, 44]

Search on the smallest value

Left Boundary set to 3

Search on the largest value

Left: 3 Middle: 9 Right: 16

Left: 3 Middle: 9 Right: 16

Right Boundary set to 10

The interval is: (3, 10)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

20 41

Target list is [20, 41]

Search on the smallest value

Left Boundary set to 4

Search on the largest value

Left: 4 Middle: 10 Right: 16

Left: 4 Middle: 6 Right: 9

Left: 7 Middle: 8 Right: 9

Left: 9 Middle: 9 Right: 9

Left: 9 Middle: 9 Right: 8

Right Boundary set to 9

The interval is: (4, 9)

Enter the list of integer values separated by spaces (all on one line), or just press enter if you are done.

*** Done ***

Process finished with exit code 0

IV. Implement intervalSearch method Consider an array of n numerical values in sorted order and a list of numerical target values Your goal is to compute the smallest range of array indices that contains all of the target values Please note that: . if a target value is smaller than data[0], the range should start with-1 . if a target value is larger than dataln-11, the range should end with n For example, given the array: 5 8 10 13 15 20 22 26 and the target values [8, 2, 9, 171, the range is (-1, 5) Devise and implement an efficient algorithm that solves this problem. HINT: 1. 2. Find the max and min in the list of target values Utilize the iterative binary search algorithm to find the position that those values would have if inserted into the list of sorted data UML diagram Interval r a first int second int m% Interval(int, int) mgetFirst0 m&toString String create int etIntervalSearch m findinterval(TI], TreeSet void main(StringO)