Binary Search

const_intervals.cpp

void rec(int from, int to, function<int(int)> f, int &i, int &p, int q, vector<array<int, 3>> &ints) {
    if (p == q)
        return;
    if (from == to) {
        ints.push_back({i, to, p});
        i = to;
        p = q;
    } else {
        int mid = (from + to) >> 1;
        rec(from, mid, f, i, p, f(mid), ints);
        rec(mid + 1, to, f, i, p, q, ints);
    }
}
void constantIntervals(int from, int to, function<int(int)> f, vector<array<int, 3>> &ints) {
    if (to <= from)
        return;
    int i = from;
    int p = f(i), q = f(to - 1);
    rec(from, to - 1, f, i, p, q, ints);
    ints.push_back({i, to, q});
}

first_to_satisfy.cpp

int binSearch(int l, int r) {
    int mid = (l+r)/2;
    if (l==r) return l;
    if (f(mid)) return binSearch(l, mid);
    else return binSearch(mid+1, r);
}

Constant intervals splits a monotonic function on [from,to) into a minimal set of half-open intervals on which it has the same value. Complexity: O(k*log(n/k))