Prpblem:

Let x1< x2 < . . . < xn be real numbers representing coordinates of n villages located along a straight road. A post office needs to be built in one of these villages.

Required:

Question1- Design an efficient algorithm to find the post-office location minimizing the average distance between the villages and the post office.

Question 2- Design an efficient algorithm to find the post-office location minimizing the maximum distance from a village to the post office.

In addition to the efficient algorithm, also describe the brute-force approach and derive the asymptotic efficiencies of each algorithm.