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. Design an efficient algorithm to find the post-office location minimizing the average distance between the villages and the post-office.
Answers
Explanation:
If we put the post office at location, the average distance between it and all the points 1 be add. Then, the sum E-k; - zis minimized when : = w/2), the point for which the number of the given points to the left of it is equal to the number of the given points to the right of it. Note that the point the In/2]th smallest called the median solves the problem for even n's as well. For a sorted list implemented as an array, the median can be found in 0(1) time by simply returning the [n/2th.element of the array. (Section 5.6 provides a more general discussion of algorithms for computing the median. b. Assuming that the points 11,12, ..., Is are given in increasing order, the answer is the point I, that is the closest to m= (1 + 2)/2, the middle point between 1 and 2. (The middle point would be the obvious...