Question

Take a look at the file GenericMethods.java.

There are three methods you must implement:

·public static <T extends Comparable<T>> int findMin(T[] arr): Iterate through the array to find the index of the smallest element in the array. If there are two elements with the smallest value, the method should return the index of the first one. The method should run in O(n).

·public static <T extends Comparable<T>> int findMinRecursive(T[] arr): Should behave just like findMin, but should be implemented recursively. Your method may not contain any while or for loops. Hint: the public findMinRecursive method should not, itself, be recursive. Instead, write an additional private helper method with additional parameters. This private helper method should be called from findMinRecursive. This must run in O(n) time.

·public static <T extends Comparable<T>> int binarySearch(T[] arr, T x): Implement a recursive binary search to find a value equal to x. Hint: The public binarySearch method, itself, should not be recursive. Instead, write an additional private helper method with additional parameters. This private helper method should be called from the public binarySearch method. This must run in O(log n) time. If the value is not found in the array, return -1. Else, return the index in the array where the value was found.

To test your code, you may compile and run GenericMethodTester.java. This tester class uses the types defined in the package shapes, which includes an interface Shape and concrete classes Rectangle, Square, and Circle. The Shape interface extends the Comparable interface, which means that the concrete classes all need to have a compareTo method. In this case, the differnt shapes are compared according to their area. Take a look at the code for these classes to make sure you understand how everything works. There is nothing you need to change in this package – it’s only here to test the GenericMethods.

Answer 1

// GenericMethods.java
public class GenericMethods {
/*
   * method that iterate through the array to find the index of the smallest element in the array.
   * If there are two elements with the smallest value, the method should return the index of the first one
   * Input array is not null
   */
   public static <T extends Comparable<T>> int findMin(T[] arr)
   {
       int minIdx = 0; // set minIdx to -1
       // loop over the array
       for(int i=0;i<arr.length;i++)
       {
           // if minIdx is not set or ith element of array < minIdx element of array, set minIdx to i
           if(minIdx == -1 || (arr[i].compareTo(arr[minIdx]) < 0))
               minIdx = i;
       }
      
       return minIdx; // return the minimum index
   }
  
   /*
   * method that recursively finds the index of the smallest element in the array.
   * Input array is not null
   */
   public static <T extends Comparable<T>> int findMinRecursive(T[] arr)
   {
       return findMinRecursive(arr, 0);
   }
  
   /*
   * helper method that recursively returns the index of the smallest element of the array
   * It takes as input the array and the start index of the array
   */
   private static <T extends Comparable<T>> int findMinRecursive(T[] arr, int startIndex)
   {
       if(startIndex == arr.length-1) // if we reach the last index of the array, return the index
           return startIndex;
       else
       {
           // get the index of minimum element of the array starting with startIndex+1
           int index = findMinRecursive(arr, startIndex+1);
           if(arr[index].compareTo(arr[startIndex]) < 0) // if element at index < element at startIndex, return index
               return index;
           else
               return startIndex; // else return startIndex
       }
   }
  
   /*
   * method to return the index of x in the array using recursion.
   * return index if x is present in arr else return -1
   * the input array arr, is sorted is ascending order
   */
   public static <T extends Comparable<T>> int binarySearch(T[] arr, T x)
   {
       return binarySearch(arr, x, 0, arr.length-1);
   }
  
   /*
   * helper method to return the index of x if found else return -1
   */
   private static <T extends Comparable<T>> int binarySearch(T[] arr, T x, int low, int high)
   {
       if(low <= high) // if low <= high
       {
           int mid = (low+high)/2; // get the mid index
           // if element at mid = x, return mid
           if(arr[mid].compareTo(x) == 0)
               return mid;
           else if(arr[mid].compareTo(x) > 0) // element at mid > x then x if present must be in the left subarray
               return binarySearch(arr, x, low, mid-1);
           else                               // element at mid < x then x if present must be in the right subarray
               return binarySearch(arr, x, mid+1,high);
       }
      
       return -1; // x not found in the array
   }
}
//end of GenericMethods.java