有一段写错了的二分代码。 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) 的函数，但是直接递推求好像也可以？ 然后二分即可。