In previous problem we wrote a method closestPairFast that on an input array of numbers, finds the distance of the closest pair by first sorting the input array and then finding the closest adjacent pair (see attached ClosestPair1D.java). In this problem, you are asked to modify the method so that it returns an integer array consisting of the indices of the closest pair in the original array. If there is a tie, return the closest pair with the smallest values. The skeleton for the new method, closestPairFast2, is provided .

The following is a sample run:

Input: 8 15 19 3 12

Return value: 1 4

Explanation: The closest pair is (15, 12). The indices of 15 and 12 in the original array are 1 and 4 respectively.

The method closestPairFast2 should have the same structure as closestPairFast and have time complexity (log ), where n is the length of the input array.

Hint: Define a helper class consisting of two attributes: (1) the value of an element and (2) its index in the original input array. Have the class implement the Comparable interface so that you can sort by value and keep the original indices

ClosestPairFast: java code below

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import java.util.Arrays;

public class ClosestPair1D {

public static long closestPairSlow(long[] A) { long min = Long.MAX_VALUE;

int n = A.length; for (int i = 0; i < n-1; i++) { for (int j = i+1; j < n; j++) { long d = Math.abs(A[i] - A[j]); if (d < min) min =d; } }

return min; }

public static long closestPairFast(long[] A) { long min = Long.MAX_VALUE;

Arrays.sort(A); for (int i = 0; i < A.length-1; i++) { long d = Math.abs(A[i] - A[i+1]); if (d < min) min =d; }

return min; }

public static void main(String[] args) { int n = 500000; long[] A = new long[n]; for (int i = 0; i < n; i++) { A[i] = (long) (Math.random() * (1L << 60)); //System.out.print(A[i] + " "); } System.out.println();

System.out.println("closestPairFast:");

long tic2 = System.currentTimeMillis(); long minDist2 = closestPairFast(A); long toc2 = System.currentTimeMillis();

System.out.printf("Minimum distance: %d ", minDist2); System.out.printf("Time: %.2f seconds ", (double)(toc2-tic2)/1000);

System.out.println(" closestPairSlow:");

long tic = System.currentTimeMillis(); long minDist = closestPairSlow(A); long toc = System.currentTimeMillis();

System.out.printf("Minimum distance: %d ", minDist); System.out.printf("Time: %.2f seconds ", (double)(toc-tic)/1000);

}

} Skelton code : closetPairFast2

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import java.util.Arrays;

public class Hw3_p1 { // HW7 Problem 2 public static int[] closestPairFast2(long[] A) { int[] ans = new int[2]; int n = A.length; ValIndexPair[] B = new ValIndexPair[n]; for (int i = 0; i < n; i++) { B[i] = new ValIndexPair(A[i], i); }

Arrays.sort(B);

// Your code starts

// Your code ends

return ans; }

public static void main(String[] args) { // Test driver for closestPairFast2 int n = 5; long[] A = new long[n]; for (int i = 0; i < n; i++) { A[i] = (long) (Math.random() * 100); System.out.print(A[i] + " "); } System.out.println(" "); int[] pairIndice = closestPairFast2(A); System.out.println("The two values are closest are at indice " + pairIndice[0] + " and " + pairIndice[1]);

n = 500000; A = new long[n]; for (int i = 0; i < n; i++) { A[i] = (long) (Math.random() * (1L << 60)); //System.out.print(A[i] + " "); } System.out.println();

System.out.println("closestPairFast2:");

long tic2 = System.currentTimeMillis(); pairIndice = closestPairFast2(A);; long toc2 = System.currentTimeMillis();

System.out.println("The two values are closest are at indice " + pairIndice[0] + " and " + pairIndice[1]); System.out.printf("Time: %.2f seconds ", (double)(toc2-tic2)/1000);

} }

class ValIndexPair implements Comparable { long val; int idx;

ValIndexPair(long val, int idx) { this.val = val; this.idx = idx; }

public int compareTo(ValIndexPair o) { if (this.val < o.val) return -1; else if (this.val == o.val) return 0; else return 1; // this.val > o.val } }