Ternary Search Implementation

dakshdixit183's blog

By dakshdixit183, history, 2 years 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 :-

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.

ternary, binary search, implementation, problem solving

dakshdixit183
2 years ago
8

Comments (6)

Show archived | Write comment?

Bit-Ghifo

2 years ago, hide # |

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

dakshdixit183

2 years ago, hide # ^ |

← Rev. 3 →

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