在 O(log(k)) 时间内找到数组中元素 x 的索引 k
Find index k of element x in array in O(log(k)) time
正在学习考试，发现了这个问题，我希望得到一些帮助。
问题：
设 A = (a_1, a_2,..., a_n) 是 n 个不同元素的排序数组，x 是 A 中的一个元素。
设计一个复杂度为O(logk)的算法来计算A中包含x的单元格的索引k（即A[k] = x）。
请注意，如果 k = theta(n)，那么标准的二分查找就可以了。但是，k 可以比 n 小很多。
让我们检查元素 a[1], a[2], a[4], ... 等等（索引是 2 的幂）直到我们找到一个大于或等于 x 的元素。这一步需要O(log k)次操作（因为当我们找到大于等于k的2的第一个幂就停止了，最多是2 ^ (log(k) + 1)）。
现在我们有一个最多包含 2 * k - 1 个元素的范围。所以我们可以应用标准的二进制搜索。它需要 O(log (2 * k - 1)) = O(log k) 次操作。
因此，总时间复杂度为O(log k).
正在学习考试，发现了这个问题，我希望得到一些帮助。
问题：
设 A = (a_1, a_2,..., a_n) 是 n 个不同元素的排序数组，x 是 A 中的一个元素。
设计一个复杂度为O(logk)的算法来计算A中包含x的单元格的索引k（即A[k] = x）。
请注意，如果 k = theta(n)，那么标准的二分查找就可以了。但是，k 可以比 n 小很多。
让我们检查元素
a[1], a[2], a[4], ...等等（索引是 2 的幂）直到我们找到一个大于或等于 x 的元素。这一步需要O(log k)次操作（因为当我们找到大于等于k的2的第一个幂就停止了，最多是2 ^ (log(k) + 1)）。现在我们有一个最多包含
2 * k - 1个元素的范围。所以我们可以应用标准的二进制搜索。它需要O(log (2 * k - 1)) = O(log k)次操作。
因此，总时间复杂度为O(log k).