arrays - 在排序数组中查找元素

Question

给定一个排序数组 A 和一个元素 x，我需要找到一个算法来返回 x 在 中的索引A 或 -1 如果 x 不在 A 中。当 d 是 A 中 x 之前出现的元素数时，算法的时间复杂度应为 Θ(logd)，或者如果 x不在A中，d是x之前的元素个数，如果他在A中。

二分查找不够好，因为它的最佳情况是 O(1)。我想从数组的开头开始，然后开始检查 2 的幂的索引。但是我迷路了。

Answer 1

你可以这样做:它使用 Θ(log d) 步来找到大小为 Θ(d) 的范围，然后在另一个 Θ(log d) 步中在该范围内进行二分查找。

int search(int[] array, int length, int valueToFind)
{
    int pos=0;
    int limit=min(length,1);
    while(limit < length && array[limit] < valueToFind)
    {
        pos=limit+1;
        limit = min(length, limit*2+1);
    }
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (array[testpos]<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    return (pos < length && array[pos]==valueToFind ? pos : -1);
}

请注意，我使用的二进制搜索不会提前退出，并且总是需要 Θ(log (limit-pos)) 时间。尽管如此，它还是比其他提前退出的搜索要快，因为它每次迭代只进行一次比较。我在这里描述其他优点:

How can I simplify this working Binary Search code in C?