Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
I would add something about: | Reply
Variants of binary search can be used on functions of other kind than monotonic:

1. Ternary search (or a binary search on the differential) can be used to find a maximum of a function which is first monotonically increasing and then monotonically decreasing.

2. Binary search can be used to find a zero of a continous function (or any function with Darboux property) such that f(0)<0, f(1)>0.

The fact 2 is rarely used in TopCoder, because in TopCoder you have to return the only (or e.g. the smallest) answer, and the binary search may return any answer. But I've used it in the Central European Programming Competition several years ago.