dakshdixit183's blog

Ternary Search Implementation
By dakshdixit183, history, 9 months ago, In English

Ternay Search is a very cool upgrade/modification on Binary Search logic There are enough resources available on this topic my favorite resource is :-

  1. CP Algorithms

This blog will include a different implementation of the approach which I found very cool 

    int l=1,r=mx;
    while(r>=l){
        int mid = (r+l)/2;
        int m1 = check(mid);
        int m2 = check(mid+1);
        if(m1>=m2){
            ans = updateAns(and,m1);
            r=mid-1;
        }
        else{
            l=mid+1;
            ans = updateAns(and,m2);
        }
    }

It would make more sense if you study the concept and then solve these 2 problems these are fairly recent problems as well

Would love any input to improve this blog.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I have this implementation that I found really helpful:

typedef long double ld;
// in case of integers , change every thing to ll and make eps = 5, then brute force the rest of the interval [l,r]
ld ternary_search(ld l, ld r){
	ld eps = 1e-12;              //set the error limit here
	while(r - l > eps){
		ld m1 = l + (r - l) / 3;
		ld m2 = r - (r - l) / 3;
		ld f1 = f(m1);      //evaluates the function at m1
		ld f2 = f(m2);      //evaluates the function at m2
		if(f1 < f2)
			l = m1;
		else
			r = m2;
	}
	return f(l);                    //return the maximum of f(x) in [l, r]
}

you just have to implement the function $$$f$$$, that depends on the problem.

→ Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    Yeah this is actual implementation of Terneray Search and how it should be used but the way I have implemented you can see it is more like Binary Search even complexity wise it would be O(log2n)

    I just always found that implementation easier

    But Yeah This is exactly how Ternary Search should be used Thanks for the Input man

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why eps=5, in case of integers?

    I think it should be 3, because when r-l<=3, then we are not able to differentiate between l,m1,m2 and r hence break out of loop.

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    time complexity?

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Yeah since difference is the derivative, it’s a smart idea

→ Reply