Binary Search Template

int firstTrue(int n) {
    int lo = 0, hi = n - 1;       // valid range: the whole thing
    int ans = -1;                 // sentinel: no True exists
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (pred(mid)) {          // True → a smaller one may exist
            ans = mid;
            hi = mid - 1;         // shrink right
        } else {                  // False
            lo = mid + 1;         // go right
        }
    }
    return ans;
}

int lastTrue(int n) {
    int lo = 0, hi = n - 1;       // valid range: the whole thing
    int ans = -1;                 // sentinel: no True exists
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (pred(mid)) {          // True → a bigger one may exist
            ans = mid;
            lo = mid + 1;         // push right
        } else {                  // False
            hi = mid - 1;         // go left
        }
    }
    return ans;
}