Hi. First you need to know what Tof means.
It literally means spit and is used when someone rips your solution apart (imagine it written on a paper). Then you add a spit to the paper and glue it back together.
In this article I'd like to introduce Tof on ternary search.
We have a function f on [A, B] and we'd like to get the minimum position in this function. More formally we'd like to find x (A ≤ x ≤ B) such that for every y (A ≤ y ≤ B), f(x) ≤ f(y).
We call this function "Ternary-Searchable" if there exists a value K such that
for all a , b with A ≤ a < b ≤ K, f(a) > f(b).
for all a , b with K ≤ a < b ≤ B, f(a) < f(b).
f on real numbers
If f is defined on all real numbers then the code will be like this
In which LOG is based on the precision you want from the answer. I use 100 or 200.
f on Integers
If f is defined on only integers you can speed it up a little bit.
The Tof
So far it has been only introduction of ternary search. from now on this article won't have any proof and it's all just Tof.
Consider f as a function on integers only.
We will partition numbers on [A, B] into sets of consecutive numbers of size S. We'll call each set of consecutive numbers a Block.
g(Block) = min(f(x)) such that x is in that Block.
Now the function g we'll be "more Ternary-Searchable" than f. :D
This method will probably work for a function like the picture below. (hand drawn since I'm too lazy to use technology)
You should determine the S considering how bad your solution is and the time limit! (I told you it's gonna be just a Tof!!)
Feel free to add as many Tof as you can to the solution. The more Tof you add the harder it gets to hack your code.
