Day 39 | Ternary Search | C++

We have learned about Binary Search, now introducing ternary search. If you remember it, then you would know it works something like this

Ternary Search is simply dividing array into 3 parts instead of two and discard 1 of those parts from our search.

Now, if you remember then there was a condition for Binary Search -

Function checking on should be monotonic.

This means that if value we are talking about then it should consistently tell if we can discard any half of the search space.

Ternary search however works on data that follows this pattern

1. Increases continuously till some point and then it keeps decreasing

2. Decreases continuously till some point and then it keeps increasing

But we will rarely use this algorithm for the thing data in an array. There will be situations when you have data like this and have to calculate the minima or maxima point.

Let's see how we can do it. Let's consider this data

We Take

mid1 = low + (high - low) / 3

mid2 = low + 2 * (high - low) / 3

We calculate F(mid1) and F(mid2) and then we find the higher value.

Notice that if

1. F(mid1) > F(mid2) Then mid1 must be towards the left side of minima, but we have no idea about mid2 Although mid2 is towards the right of minima in the diagram, there are values where comparison hold but mid2 is smaller than the minima In this situation, we move low = mid1
   

2. F(mid1) < F(mid2) Then mid2 must be towards the right side of minima, but we have no idea about mid1 In this situation, we move high = mid2

In the case of equality, I follow any step.

And you will discard 1/3 of the search space in a move. So you will be running code in log(N) [But this will be base 3 log unlike base 2 log in binary search]

Let's solve Meeting on the Line

Input

7
1
0
3
2
3 1
0 0
2
1 4
0 0
3
1 2 3
0 0 0
3
1 2 3
4 1 2
3
3 3 3
5 3 3
6
5 4 7 2 10 4
3 2 5 1 4 6

Output

0
2
2.5
2
1
3
6

This problem is a direct use case of Ternary Search. Like calculate the cost and run Ternary Search like this

Btw better to overuse long double instead of getting a WA

#include<bits/stdc++.h>
using namespace std;

long double cost_at(long double x0, vector<int> &x, vector<int>& t){
    long double cost = 0;
    for(int i = 0; i < x.size(); i++){
        cost = max(cost, t[i] + abs(x0 - x[i]));
    }
    return cost;
}

void solve(){
    int n;
    cin >> n;
    vector<int> x(n),t(n);
    for(int &i: x)cin >> i;
    for(int &i: t)cin >> i;
    long double lo = 0, hi = 1e15;
    for(int i = 0; i < 200; i++){
        long double mid1 = lo + (hi - lo) / 3;
        long double mid2 = hi - (hi - lo) / 3;
        long double f1 = cost_at(mid1, x, t);
        long double f2 = cost_at(mid2, x, t);
        if(f1 > f2){
            lo = mid1;
        }else{
            hi = mid2;
        }
    }
    cout << fixed << setprecision(12) << lo << "\n";
}

int main(){
    int t;
    cin >> t;
    while(t--)solve();
}

Please like and share my posts if they are helpful.