Question 3. ( 30 points) Recall that we have discussed the recursion-based binary search algorithm, the worst-case running time can be represented by a recurrence relation: T(n)=T(2n)+d. For the closest pair problem ( S is a set of n points on a line (1-dimensional, unsorted), find the shortest distance of two points among these n points, e.g., input: S=[1,5,8,2,15], output: d=1), the recursion-based algorithm (divide-and-conquer) can be used to find the solution, the basic idea behind the algorithm design is: 1. Divide the set S of n points by some point mid S into two sets S1 and S2 such that p