T2

有一段写错了的二分代码。

int bs(int n, int* a, int x) {
    int l = 1, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return l;
}

将长度为 n 时无法返回的下标总数记为 f(n)。

记 g(n) = f(n) + f(\lfloor \frac{n}{2} \rfloor) + f(\lfloor \frac{n}{4} \rfloor) + \dots + f(0)。

求能够使得 g(n) >= k 的最小初始数组长度 n。



核心结论：一个下标永远不会被返回，当且仅当它曾作为某个长度 >= 3 的区间的 mid 被选中。（易证）
f(n) = f(mid - 1) + f(n - mid) + 1。
发现 f(n) 有规律，可以写出 O(1)（记不清了，也可能是 O(log n)）求 f(n) 的函数，但是直接递推求好像也可以？
然后二分即可。