In a little town there are n houses on the main street. This street runs along the x-axis and the coordinates of the houses are x1; x2; . ; xn.

In a little town there are n houses on the main street. This street runs along the x-axis and the coordinates of the houses are x1; x2; .. ; xn. You decided to open a candy shop and you want to find the most profitable coordinate xbest . The most profitable coordinate will be one that minimizes the sum of the distances to every house. Give an O(n) algorithm that finds xbest such that distbest:= ∑i=1 to n|xbest − xi| is as small as possible