Talk:Ternary search

From Wikipedia, the free encyclopedia

I'm reacting to the version by Shreevatsa.

Consider the sequence {3, 3, 3, 3, 3, 3, 3, 1000, 3}. It satisfies your definition of a unimodal sequence, but your algorithm fails to find the minimum. (Here, it's the definition that's wrong, you need the sequence to be strictly increasing/decreasing.)

Also, your constraints fail to mention f(x), thus this: {10, 20, 30, 40, -10000, 40, 30, 20, 10} satisfies them.

And the article is IMHO fundamentally misleading. For sequences there are better algorithms, such as: look at the elements x=floor((left+right)/2) and x+1. Ternary search is used for functions, because it is simple to code and numerically stable.

-- misof

Changed to functions, removed unimodal and monotonic references. --Enogipe

Well, there are also better algorithms for functions: If one uses the golden ratio instead of thirds, the interval size shrinks to 0.618... instead of 0.666... and one can reuse expensively calculated function values (one function evaluation instead of two per iteration). -- hagman

One-third and one-third and two-thirds makes four-thirds which is greater than one...

-- silentOpen