在O（log（m））的时间内在排序数组中搜索整数k，其中m是k之前的元素数？

Question

我的班级已获得以下任务：

找到一个接收排序的数组和整数k作为参数并返回数组中k的index的算法。如果k不在数组中，则返回-1。

到目前为止，很好。这是我卡住的地方：

时间复杂度要求： O（log（m））其中m是k之前的元素数。如果k不在数组中，则m是最接近k的元素之前的元素数。

提示：搜索步骤应成指数增长，而不必从中间开始。

Bonus：我们每个人都必须以不同的语言实现相同的算法，所以我很喜欢伪代码的解释，因为这对我向朋友们解释很有帮助。第二优先级是Java。尽管如此，任何帮助将不胜感激！

提前感谢您，请注意安全！

Answer 1

您正在寻找Exponential search。

在指数搜索中，我们将索引从0以2的幂开始跳跃，直到达到一个索引，该索引的值高于我们要寻找的数字。也就是说，假设数字在索引14处，我们跳到索引16并停止，因为第16个索引中的数字大于我们的数字。时间复杂度为O(log m)，因为我们停止通过2的幂经过m的瞬间。

比我们在0和在上一步中停止的索引之间执行二进制搜索。为什么？由于现在上下限之间的数字不超过2m，因此二进制搜索的时间复杂度为O(log (2m))，即O(log m)，我们完成了！

伪代码：

exponential_search:
 Array A 
 Key k

1. i = 1
2. while A[i - 1] < k and i <= size of A
2.1.  i = i * 2

// Now i is no more than 2 * m

3. perform binary search with k and A between 0 and i
4. return the binary search's result