对于O（log（m））时间复杂度的最佳搜索方法是什么？

Question

我正在寻找最好的搜索算法，该算法返回O（log（m））中排序数组中元素的索引，其中m是k之前的元素数。注：如果k不在数组中，则m是最接近k的元素之前的元素数。

我想到了一个搜索，其中每个步骤都呈指数增长，而不必从中间开始。

Answer 1

首先，让我们尝试使k的范围尽可能小。我们将查看元素a[0], a[1], a[2], ... a[2 ** i], ...，直到找到一个大于k的元素。假设我们在索引r处停止。然后我们可以肯定地知道，因为数组已排序，所以如果k在数组中，则其位置m小于r。对时间复杂度至关重要的另一个事实是m > i/2。这是正确的，因为在上一步中，我们查看了a[r/2]，它小于k。

如果对子数组a[0 ... r]运行简单的二进制搜索，则会在k中找到O(log r)。查找r的步骤总数为O(log r)。从r > m > r/2开始，确实是log r > log m > log r - 1。因此，我们可以将O(log r)重写为O(log m)，这正是我们所需要的。

这是我在Python 3中的解决方案：

def find(a, k):
    if a[0] > k:
        return -1

    r = 1
    while r < len(a):
        if a[r] > k:
            break
        r *= 2

    if r >= len(a):
        if a[-1] < k:
            return -1
        r = len(a) - 1

    l = -1
    while r - l > 1:
        m = (l + r) // 2
        if a[m] < k:
            l = m
        else:
            r = m

    if a[r] == k:
        return r   
    else:
        return -1

Answer 2

您正在寻找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