Ternary search

2016-02-18 2024-05-07 algorithmspost

Hi! This time I going to talk about a new technique I’ve just learned, Ternary Search.

Ternary search

Ternary search is a technique similar to Binary Search and is important since ternary search could success in situations where the binary search would fail. Time ago I was very criticized in the Codeforces forum for arguing that has no sense to use ternary search if it is not more efficient than binary search. Is not about efficiency but –said the others. Actually I meant to ternary search in arrays, to reduce the search space to a third part, etc. Now I understand what they were talking about.

Sample problem

You can solve the 1146 - Closest Distance problem from lightoj.com with this technique.

Solution to sample problem

Basic idea

Compute the distance between the two men as they move and take the minimum distance.

Termnary search example

Obviously, we can only take discrete points, and, since the problem ask for an answer with an error less than 1e-6, a brute force approach would take much time, very much. So the strategy is to use ternary search:

Step 1 Step 2 Step 3 Step 4

And so on. Here is my solution:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <complex>
#include <algorithm>
#define x() real()
#define y() imag()

using namespace std;

typedef complex<double> Vector;
typedef complex<double> point;
point points[5];

double closest()
{
    Vector A = points[1] - points[0];
    Vector B = points[3] - points[2];
    Vector unita = A/abs(A);
    Vector unitb = B/abs(B);
    point startA = points[0];
    point startB = points[2];

    double maxa = abs(A);
    double mina = 0;
    double maxb = abs(B);
    double minb = 0;
    double ta, tb, ans = 1000;
    point a, b, c, d;

    int count = 500;
    while (count--) {
        ta = abs(maxa - mina)/3;
        tb = abs(maxb - minb)/3;
        a = (unita * (mina + ta)) + startA;
        b = (unitb * (minb + tb)) + startB;

        ta += ta;
        tb += tb;
        c = (unita * (mina + ta)) + startA;
        d = (unitb * (minb + tb)) + startB;

        if (abs(b - a) < abs(d - c)) {
            maxa = maxa - ta/2;
            maxb = maxb - tb/2;
            ans = std::min(ans, abs(b - a));
        } else {
            mina = mina + ta/2;
            minb = minb + tb/2;
            ans = std::min(ans, abs(d - c));
        }
    }

    return ans;
}

int main(int argc, char **argv)
{
    int t, tc, i;
    double x, y;

    scanf("%d", &t);

    for (tc = 1; tc <= t; tc++) {
        for (i = 0; i < 4; i++) {
            scanf("%lf %lf", &x, &y);
            points[i] = point(x, y);
        }

        printf("Case %d: %.10lf\n", tc, closest());
    }

    return 0;
}

References

1 Ternary search
2 Codeforces discussion about ternary search
3 Topcoder discussion about ternary search