Author |
Topic: Ternary Search Algorithm (Read 5423 times) |
|
Skandh
Junior Member
Gender: 
Posts: 77
|
 |
Ternary Search Algorithm
« on: Apr 14th, 2011, 11:08am » |
 Quote  Modify
|
I was going through Ternary Search Algorithm on wikipedia [ http://en.wikipedia.org/wiki/Ternary_search ], it's described as:
"A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function (function that is either strictly increasing and then strictly decreasing or vice versa)."
But example demonstrates it like any typical search algorithm (like binary search) with O(lg n ) complexity. Can you please explain how it is useful in finding minimum or maximum of a unimodal function?
Thanks
|
|
 IP Logged |
I wanna pull by legs!!!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Ternary Search Algorithm
« Reply #1 on: Apr 15th, 2011, 12:41am » |
Quote Modify
|
You are right.
It looks like the example doesn't do what it is supposed to do, which is to search for a minimum or maximum.
And it seems to me it doesn't even do correctly what it seems it wants to do, namely check that an element k is present in an array that is increasing then decreasing.
- If the element is present in the third part, it might search for it in the 1st part and fail to find it.
- If the element k is larger than any element in the array, it fails to stop.
The correct way to implement ternary search would be something like:
To search for a max of f in [x,y]:
- choose z,t | x<z<t<y
- if f(z)<f(t) then the maximum must be right of z, so continue searching in ]z,y]
- if f(z)>f(t) then the maximum must be left of t, so continue searching in [x,t[
- if f(z)=f(t) you are in trouble, unless the function is strictly increasing and strictly decreasing. In that case, the maximum is between z and t, so continue searching in [z,t]
- stop when the interval is small enough
|
| « Last Edit: Apr 15th, 2011, 12:41am by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
For reference, here is the original algorithm from the Wikipedia page.
I deleted it because it is obviously wrong. 
PS: funnily, the following pages gives a correct algorithm, giving Wikipedia as a source.
http://in.answers.yahoo.com/question/index?qid=20100217055527AAuK4iB
PS2: I restored the correct algorithm from Wikipedia's history.
|
| « Last Edit: Apr 15th, 2011, 1:25am by Grimbal » |
IP Logged |
|
|
|
Skandh
Junior Member
Gender:
Posts: 77
|
|
Re: Ternary Search Algorithm
« Reply #3 on: Apr 15th, 2011, 9:29am » |
Quote Modify
|
Thanks a lot, Grimbal.
|
|
IP Logged |
I wanna pull by legs!!!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
tsearch.txt