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 in Figure 18-10 and the target values (8, 2, 9, 17), the range is -1 to 5.

a. Devise an efficient algorithm that solves this problem.

b. If you have n data values in the array and m target values in the list, what is the Big Oh performance of

your algorithm?

c. Implement and test your algorithm

Figure 8-10: An array

[5] [8] [10] [13] [15] [20] [22] [26]

0 1 2 3 4 5 6 7

====================CODE===========================

***Driver.java

import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.Scanner; /**A demonstration of the class IntervalFinder.

@author Charles Hoot @version 4.0 */ public class Driver { public static void main(String args[]) { Random generator = new Random();

final int N = 15;

// Generate a random array of integers Integer sortedData[] = new Integer[N]; List targets = null; for(int i = 0; i < N; i++) { Integer value = generator.nextInt(10); sortedData[i] = value;

// Guarantee is larger than the last value if (i > 0 && sortedData[i] < sortedData[i-1]) sortedData[i] += sortedData[i-1]; } // end for

System.out.println("The sorted data is:"); for (int i = 0; i < N; i++) System.out.print(sortedData[i] + " "); System.out.println();

targets = getTargetValues();

boolean done = (targets.size() == 0); while (!done) { Interval result = IntervalFinder.findInterval(sortedData, targets); System.out.println("The pair of indices that bound the interval " + "containing the given values is " + result); System.out.println(); targets = getTargetValues(); done = (targets.size() == 0); } // end while

System.out.println("Goodbye!"); } // end main

/** Initializes the list of ints by reading them from the keyboard. @return A list of integers. */ public static List getTargetValues() { List result = new ArrayList<>(); System.out.println("Enter the list of integer values (all on one line), " + "or just press enter if you are done."); Scanner fromKeyboard = new Scanner(System.in); String values = fromKeyboard.nextLine();

Scanner dataValues = new Scanner(values);

while (dataValues.hasNextInt()) { int data = dataValues.nextInt(); result.add(new Integer(data)); } // end while

return result; } // end getTargetValues } // end Driver

/* The sorted data is: 2 6 6 6 9 10 14 21 26 27 33 40 46 46 52 Enter the list of integer values (all on one line), or just press enter if you are done. 2 52 The pair of indices that bound the interval containing the given values is (0, 14)

Enter the list of integer values (all on one line), or just press enter if you are done. 7 42 20 The pair of indices that bound the interval containing the given values is (3, 12)

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

Goodbye!

*/

***Interval.java

/** A class that represents an interval in an array.

@author Charles Hoot @version 4.0 */ public class Interval { private int lower, upper; // The first and second bounds

public Interval(int lowerBound, int upperBound) { lower = lowerBound; upper = upperBound; } // end constructor

/** Returns the lower bound of the interval. @return The lower bound of the interval. */ public int getLower() { return lower; } // end getFirst

/** Returns the upper bound of the interval. @return The upper bound of the interval. */ public int getUpper() { return upper; } // end getSecond

public String toString() { return "(" + lower + ", " + upper + ")"; } // end toString } // end Interval

* Please make the answer base on the code.

* Make comments as well. Thank you!