It seems, there are so many materials on binary search already that everyone must know how to code it, however every material seems to tell its own approach, and I see people being lost and still making bugs on such a simple thing. That's why I want to tell you about an approach which I find the most elegant. Of all the variety of articles, I saw my approach only in this comment (but less generalized).

UPD: Also in the nor's blog.

The problem

Suppose you want to find the last element less than x in a sorted array and just store a segment of candidates for the answer [l, r]. If you write:

int l = 0, r = n - 1; // the segment of candidates
while (l < r) { // there are more than 1 candidate
    int mid = (l + r) / 2;
    if (a[mid] < x) {
        l = mid;
    } else {
        r = mid - 1;
    }
}
cout << l;

...you will run into a problem: suppose l = 3, r = 4, then mid = 3. If a[mid] < x, you will end up in a loop (the next iteration will be again on [3, 4]).

Okay, it can be fixed with rounding mid up – mid = (l + r + 1) / 2. But we have another problem: what if there are no such elements in the array? We would need an extra check for that case. As a result, we have a pretty ugly code that is not generalized very well.

My approach

Let's generalize the problem we want to solve. We have a statement about an integer number n that is true for integers smaller than some bound, but then always stays false once n exceeded that bound. We want to find the last n for which the statement is true.

First of all, we will use half-intervals instead of segments (one border is inclusive, another is non-inclusive). Half-intrevals are in general very useful, elegant and conventional in programming, I recommend using them as much as possible. In that case we will choose some small l for which we know in before the statement is true and some big r for which we know it's false. Then the range of candidates is [l, r).

My code for that problem would be:

int l = -1, r = n; // a half-interval [l, r) of candidates
while (r - l > 1) { // there are more than 1 candidate
    int mid = (l + r) / 2;
    if (a[mid] < x) {
        l = mid; // now it's the largest for which we know it's true
    } else {
        r = mid; // now it's the smallest for which we know it's false
    }
}
cout << l; // in the end we are left with a range [l, l + 1)

The binary search will only do checks for some numbers strictly between initial l and r. It means that it will never check the statement for l and r, it will trust you that for l it's true, and for r it's false. Here we consider -1 as a valid answer, which will correspond to no numbers in array being less than x.

Notice how there are no "+ 1" or "- 1" in my code and no extra checks are needed, and no loops are possible (since mid is strictly between the current l and r).

Reverse problem

The only variation that you need to keep in mind is that half of the times you need to find not the last, but the first number for which something is true. In that case the statement must be always false for smaller numbers and always true starting from some number.

We will do pretty much the same thing, but now r will be an inclusive border, while l will be non-inclusive. In other words, l is now some number for which we know the statement to be false, and r is some for which we know it's true. Suppose I want to find the first number n for which n * (n + 1) >= x (x is positive):

int l = 0, r = x; // a half-interval (l, r] of candidates
while (r - l > 1) { // there are more than 1 candidate
    int mid = (l + r) / 2;
    if (mid * (mid + 1) >= x) {
        r = mid; // now it's the smallest for which we know it's true
    } else {
        l = mid; // now it's the largest for which we know it's false
    }
}
cout << r; // in the end we are left with a range (r - 1, r]

Just be careful to not choose a r too large, as it can lead to overflow.

An example

1201C - Maximum Median You are given an array a of an odd length n and in one operation you can increase any element by 1. What is the maximal possible median of the array that can be achieved in k steps?

Consider a statement about the number x: we can make the median to be no less than x in no more than k steps. Of course it is always true until some number, and then always false, so we can use binary search. As we need the last number for which this is true, we will use a normal half-interval [l, r).

To check for a given x, we can use a property of the median. A median is no less than x iff at least half of the elements are no less than x. Of course the optimal way to make half of the elements no less than x is to take the largest elements.

Of course we can reach the median no less than 1 under given constraints, so l will be equal to 1. But even if there is one element and it's equal to 1e9, and k is also 1e9, we still can't reach median 2e9 + 1, so r will be equal to 2e9 + 1. Implementation:

#define int int64_t

int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
sort(a.begin(), a.end());
int l = 1, r = 2e9 + 1; // a half-interval [l, r) of candidates
while (r - l > 1) {
    int mid = (l + r) / 2;
    int cnt = 0; // the number of steps needed
    for (int i = n / 2; i < n; i++) { // go over the largest half
        if (a[i] < mid) {
            cnt += mid - a[i];
        }
    }
    if (cnt <= k) {
        l = mid;
    } else {
        r = mid;
    }
}
cout << l << endl;

Conclusion

Hope I've made it clearer and some of you will switch to this implementation. To clarify, occasionally other implementations can be more fitting, for example with interactive problems – whenever we need to think in terms of an interval of searching, and not in terms of the first/last number for which something is true.

I remind that I do private lessons on competitive programming, the price is $30/h. Contact me on Telegram, Discord: rembocoder#3782, or in CF private messages.