修改二进制搜索以查找大于 x 且小于 2x 的数组中的所有整数，时间复杂度优于 O(n)

Question

令 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

Answer 1

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

由于您正在使用 python，bisect 模块可以帮助您进行二分查找。

Answer 2

我的使命是改进每个人的默认二分搜索。正如我在这个答案中所描述的：How can I simplify this working Binary Search code in 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 单独放置而不是将其重置为零即可实现。

修改二进制搜索以查找大于 x 且小于 2x 的数组中的所有整数，时间复杂度优于 O(n)

Modify binary search to find all integers in an array bigger than x and less than 2x with a time- complexity better than O(n)

algorithm

time-complexity

binary-search

analysis