Here we are asked to find the appropriate optimal point $P_k$ from which the distance between S to D is least. Thus the point would be where the distance between S and the point is somewhere close to the distance between the point and D.
Let y` be y1 and y`` be y2 and the array sorted in decreasing order be Y.
Using the below method we get the optimal point.
getMinPointOnLine(int[] Y, int y1, int y2):
int low = 0, high = Y.length – 1, mid = 0;
while( low <= high ) {
mid = low + (high – low) / 2;
int diff_y1 = Math.abs(y[mid] – y1);
int diff_y2 = Math.abs(y[mid] – y2);
if(diff_y1 == diff_y2) return mid;
else if(diff_y1 < diff_y2) low = mid + 1;
else high = mid – 1;
}
return mid;
To decrease the overall cost we will modify low and high params so be on the side whose height difference is greater with current point so that on the next iteration our overall cost gets reduced.