Alright, round 4.

This time it's binary search. The code looks normal, the idea seems reasonable, and it even works on the examples I tried.

But I'm pretty sure there's a test case waiting to ruin my day.

The problem

You are given a sorted array of n integers and an integer x.

Find the index of the first element that is greater than or equal to x. If no such element exists, print -1.

Use 0-based indexing.

My solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> a(n);
    for (int &i : a) cin >> i;

    int l = 0, r = n - 1, ans = -1;

    while (l < r) {
        int mid = (l + r) / 2;

        if (a[mid] >= x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << '\n';
}

The idea is simple: if a[mid] is at least x, save that position and search to the left. Otherwise, search to the right.

Pretty standard binary search, right?

Your mission

Find the smallest counterexample you can.

• Give an input for which my code prints the wrong answer.
• Explain exactly why it fails.
• Fix the code with as few changes as possible.
• Bonus: can you explain what invariant a correct binary search should maintain?

Please don't just say "use lower_bound." I know it exists. I want to see the actual bug.

Let's see who catches it first.