ternary search

help
,
1

I am trying to learn ternary search and came across a problem “plant location” at codechef.

I am really not getting how ternary search can be applied in this problem. When I read about it at wiki it talks about function with one minimum or maximum but in this problem how one can estimate that there is only one point which is optimum(i mean only one point whose sum of distance from all points is minimum)? Secondly how we can decide it is ternary search not binary search that should be used?I am really confused on this issue.

If someone can provide any links that are related to ternary search i will be really greatful.

Thanks.

Problem link: http://www.codechef.com/problems/K1/

1 Like
2

Binary search is for monotonic functions.

For this question, consider the two infinite end points of the line. As the two points move closer to each other the sum of distances decreases and reaches a minimum at a single point.

Else consider it like this. If we move from one end point to another and plot a graph of sum of distances, this graph will be “U” shaped. What we are looking for is the bottommost point of this “U”.

Just try to implement binary search on this “U” shaped graph and you will know why it is WRONG.