-2

令 A 是一个包含 n 个不同正整数的排序数组。令 x 为正整数，使得 x 和 2x 都不在 A 中。

描述一种有效的算法来找出 A 中大于 x 且小于 2x 的整数个数

算法的复杂度是多少？有人可以在不使用库的情况下编写伪代码吗？

我知道这可以通过线性时间复杂度来完成，但可以修改二进制搜索来实现这一点。以下是我想出的线性时间复杂度解决方案

def find_integers(A, x):
    integers = 0
    for element in A:
        if element > x and element < 2*x:
            integers += 1
    return integers
4

2 回答 2

2

正如您已经发现的那样，您可以使用二进制搜索。搜索 x 和 2x 并注意列表中的位置，您可以根据两个位置之间的差异计算整数个数。

由于您使用的是 python，因此bisect模块可以帮助您进行二进制搜索。

于 2019-02-13T02:35:25.790 回答
0

我的任务是改进每个人的默认二进制搜索。正如我在这个答案中所描述的：如何在 C 中简化这个工作二进制搜索代码？...

...几乎我所有的二进制搜索都搜索位置而不是元素，因为它更快更容易正确。

它也很容易适应这样的情况：

def countBetweenXand2X(A,x):
    if x<=0:
        return 0

    # find position of first element > x

    minpos = 0
    maxpos = len(A)
    while minpos < maxpos:
        testpos = minpos + (maxpos-minpos)//2
        if A[testpos] > x:
            maxpos = testpos
        else:
            minpos = testpos+1

    start = minpos;

    # find position of first element >= 2x

    maxpos = len(A)
    while minpos < maxpos:
        testpos = minpos + (maxpos-minpos)//2
        if A[testpos] >= x*2:
            maxpos = testpos
        else:
            minpos = testpos+1

    return minpos - start

这只是 2 次二进制搜索，因此复杂度仍然为O(log N)。另请注意，第二次搜索从第一次搜索中找到的位置开始，因为我们知道第二个位置必须是>=第一个。我们只是通过离开minpos而不是将其重置为零来实现这一点。

于 2019-02-13T03:16:50.233 回答