在排序数组中查找元素 [英] Find element in a sorted array

问题描述

给定一个排序后的数组 A 和一个元素 x ，我需要找到一种算法，该算法返回 x 在中的索引如果 x 不在 A 中，则为A 或 -1 .当d是 A 中 x 之前出现的元素数，或者如果< x 不在 A 中，d是 x 之前的元素数(如果他在 A 中).

Given a sorted array A and an element x, I need to find an algorithm that returns the index of x in A or -1 if x is not in A. the time complexity of the algorithm should be Θ(logd) when d is the number of elements that appears before x in A, or if x is not in A, d is the number of elements that were before x if he was in A.

二进制搜索不够好，因为其最佳情况是O(1).我想到从数组的开头开始，开始检查2的幂的索引，但是我迷路了.

Binary search is not good enough because its best case is O(1). I thought of starting from the beginning of the array, and start checking the indexes that are powers of 2. but I got lost.

推荐答案

您可以这样操作:它使用Θ(log d)步骤查找大小为Θ(d)的范围，然后在其中进行二进制搜索在另一个Θ(log d)步骤中达到该范围.

You can do it like this: It uses Θ(log d) steps to find a range of size Θ(d), and then does a binary search in that range in another Θ(log d) steps.

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))时间.即使这样，它也比其他早退出的搜索要快，因为它每次迭代仅进行一次比较.我在这里描述了其他优点:

Note that the binary search I use does not exit early, and always takes Θ(log (limit-pos)) time. Even so it's faster than other searches that do exit early, because it does only one comparison per iteration. I describe other advantages here:

我如何简化使用C的工作二进制搜索代码?

这篇关于在排序数组中查找元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！