Consider an array data of n numerical values in sorted order and a list of numerical target values (target values are not necessarily sorted). 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 an efficient algorithm that solves this problem and implement it in

public static >

Interval findInterval(T[] sortedData, List targetValues)

where Interval is a class that provides two public methods getLower() and getUpper() to return the lower and upper values of an Interval object. Implement the Interval class.

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?

ArraySearcher.java

/** A class of static methods for searching an array of Comparable objects. */ public class ArraySearcher { // Segment 18.3 /** Searches an unsorted array for anEntry. */ public static boolean inArrayIterativeUnsorted(T[] anArray, T anEntry) { boolean found = false; int index = 0; while (!found && (index < anArray.length)) { if (anEntry.equals(anArray[index])) found = true; index++; } // end while return found; } // end inArrayIterativeUnsorted // ======================================================================================== // Segment 18.6 /** Searches an unsorted array for anEntry. */ public static boolean inArrayRecursiveUnsorted(T[] anArray, T anEntry) { return search(anArray, 0, anArray.length - 1, anEntry); } // end inArrayRecursiveUnsorted // Searches anArray[first] through anArray[last] for desiredItem. // first >= 0 and < anArray.length. // last >= 0 and < anArray.length. private static boolean search(T[] anArray, int first, int last, T desiredItem) { boolean found = false; if (first > last) found = false; // No elements to search else if (desiredItem.equals(anArray[first])) found = true; else found = search(anArray, first + 1, last, desiredItem); return found; } // end search // ========================================================================================

/** Searches a sorted array for anEntry. */ public static > boolean inArrayRecursiveSorted(T[] anArray, T anEntry) { return binarySearch(anArray, 0, anArray.length - 1, anEntry); } // end inArrayRecursiveSorted // Segment 18.13 // Searches anArray[first] through anArray[last] for desiredItem. // first >= 0 and < anArray.length. // last >= 0 and < anArray.length. private static > boolean binarySearch(T[] anArray, int first, int last, T desiredItem) { boolean found; int mid = first + (last - first) / 2; if (first > last) found = false; else if (desiredItem.equals(anArray[mid])) found = true; else if (desiredItem.compareTo(anArray[mid]) < 0) found = binarySearch(anArray, first, mid - 1, desiredItem); else found = binarySearch(anArray, mid + 1, last, desiredItem); return found; } // end binarySearch // ========================================================================================

public static void display(T[] anArray) { System.out.print("The array contains the following entries: "); for (int index = 0; index < anArray.length; index++) { System.out.print(anArray[index] + " "); } // end for System.out.println(); } // end display } // end ArraySearcher

ArraySort.java

import java.util.* ; public class SortArray { public static > void selectionSort(T[] a, int n) { for (int index = 0; index < n - 1; index++) { int indexOfSmallest = indexOfSmallest(a, index, n - 1); T temp = a[index]; a[index] = a[indexOfSmallest]; a[indexOfSmallest] = temp; //Invariant: a[0] <= a[1] <= . . . <= a[index] <= all other a[i] } // end for } // end selectionSort private static > int indexOfSmallest(T[] a, int first, int last) { T min = a[first]; int indexOfMin = first; for (int index = first + 1; index <= last; index++) { if (a[index].compareTo(min) < 0) { min = a[index]; indexOfMin = index; } } return indexOfMin; }

public static > void insertionSort(T[] a, int n) { for(int unsorted = 1; unsorted < n; ++unsorted) { T item = a[unsorted]; int loc = unsorted; while(loc > 0 && a[loc-1].compareTo(item) > 0) { a[loc] = a[loc-1]; --loc; } a[loc] = item; } }

public static > void bubbleSort(T[] a, int n) { for(int pass = 1; pass < n ; ++pass) { for(int index = 0; index < n-pass; ++index) { int nextIndex = index + 1; if(a[index].compareTo(a[nextIndex]) > 0) { T temp = a[index]; a[index] = a[nextIndex]; a[nextIndex] = temp; } } } }

public static > void bubbleSort2(T[] a, int n) { boolean sorted = false; for(int pass = 1; pass < n && !sorted ; ++pass) { sorted = true; for(int index = 0; index < n-pass; ++index) { int nextIndex = index + 1; if(a[index].compareTo(a[nextIndex]) > 0) { T temp = a[index]; a[index] = a[nextIndex]; a[nextIndex] = temp; sorted = false; } } } } public static void main(String [] args) { Integer [] a = { 15, 8 , 10 , 2, 5 }; //selectionSort(a, a.length); //insertionSort(a, a.length); //bubbleSort(a, a.length); bubbleSort2(a, a.length); System.out.println("a = " + Arrays.toString(a)); } } // end SortArray