Problem 5 (20 points) We have learned that Mergesort sorts an array of numbers in ( log) time, and

Binary Search determines if a given number is present in a sorted array of numbers in (log)

time.

Describe an ( log) time algorithm that takes as input an array with distinct numbers (not

necessarily sorted) and returns the number of Good pairs in . We say a pair of integers (, ) is

Good iff both and are in A,

its running time. (Your algorithm can use mergesort and binary search as black-box.)

Example: Given array = [8, 3, 4, 1] and = 5, the Good pairs are [(1, 3), (1, 4)]. So, you should

output 2.

lem 5 (20 points) We have learned that Mergesort sorts an array of n numbers in O(nlogn) time, and Binary Search determines if a given number is present in a sorted array of n numbers in O(logn) time. Describe an O(nlogn) time algorithm that takes as input an array A with n distinct numbers (not necessarily sorted) and returns the number of Good pairs in A. We say a pair of integers (x,y) is Good iff both x and y are in A, x