Блог пользователя dakshdixit183

Ternary Search Implementation
Автор dakshdixit183, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
3 года назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить