Binary Search Notes

You need to be mainly careful with your termination condition, how you calculate the middle element and how you assign the boundary values.

Let’s say the array outputs the following values for the condition f¹

F F F F F F T T T T T  
          ^ ^  
          A B  

Point A : Last element where the condition is false.
Point B : First element where the condition is true.

// Goal : Find first `True` in [l, r) interval

int l = 0, r = mx;
while(l < r){
    int m = l + (r - l) / 2;
    if( f(m) ){
        r = m;
    }else{
        l = m + 1;
    }
}

cout << l << endl;

// l        == Point B
// l - 1    == Point A

Ternary Search

The cp-algorithm article or wikipedia will do more justice on explaining this, but my quick notes is as follows.

Imagine You have a function which has a single minima or maxima (think about the f(x) = x^2 function). Your task is to find the value at which it minimises or maximises.

Let’s say the function is initially strictly decreasing, and then after the minima it is strictly increasing. In this case you can find the minima with terminary search algorithm.

You divide the range in 3 parts by creating to mid points at 1/3 and 2/3 range. You compare the value of function at these points and update the boundaries.

When you don’t want to worry about corner cases, do it with eps tolerance like below.

int l = 0; r = mx;

int eps = 3;

while(r - l > eps){
    int m1 = l + (r - l) / 3;
    int m2 = r - (r - l) / 3;

    if (f(m1) < f(m2)){
        r = m2;
    }else{
        l = m1;
    }
}

repA(i, l, r){
    // calcualte for the answer
}

Other potential way to code

The reason I am hiding this is because I have not properly thought it through if this will work in all the scenarios. Something to do in future. I feel that the `eps` method above generally works well and we shouldn't need to case work each scenario so hiding this is better.

int l = 0; r = mx;
while(l < r){
    int m1 = l + (r - l) / 3;
    int m2 = r - (r - l) / 3;

    if (cost(m1) < cost(m2)){
        r = m2 - 1;
    }else{
        l = m1 + 1;
    }
}

cout << l << endl;

Example problem for ternary search: CSES 1074

Reference

• Binary search and other “halving” methods - nor’s blog

1. For the normal binary search to find the position of given value in the array, the f(val) can be val >= search_term. ↩