2

I have learned that finding the minimum/maximum of an unimodal function can be done with ternary search, an algorithm that runs in O(logN) time (where N is the size of the given search range).

However, I recently had the thought that maybe we could accomplish finding the max/min of an unimodal function with binary search as well. Specifically, for functions that have a definite maximum, we could find and return the first x-value for which f(x) >= f(x+Epsilon) (where Epsilon is the allowed error bound). On the other hand, for functions that have a definite minimum, we could find and return the first x-value such that f(x) <= f(x+Epsilon).

Overall, my question is, why is ternary search used at all for this search operation if binary search can accomplish the same applications? Am I missing something here, or have I made some other logical mistake?

Christopher Miller
  • 861
  • 4
  • 9

2 Answers2

0

There are some scenarios where binary search wont be helpful but ternary search can yield desired results.

Here is a resource that helps you understand in detail about it.

Serial Lazer
  • 1,667
  • 1
  • 7
  • 15
0

Let f(x) = -x^2 + 3. Let Epsilon = 2.

The first x-value for which f(x) >= f(x+Epsilon) is -1:

f(-1) = 2 = f(-1 + 2) = f(1) = 2

But the answer is x = 0.

גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
  • If `Epsilon` is the allowed error bound though, wouldn't the answer of `-1` would be acceptable in this context because it is less than 2 away from the true correct answer, which is `0`? – Telescope Nov 15 '20 at 18:25
  • @Telescope OP stated in the question description: "we could accomplish finding the max/min of an unimodal function with binary search." What you are suggesting is not "the max/min." – גלעד ברקן Nov 15 '20 at 19:27