arrays - 检查排序数组 A 中是否存在 A[i] = 2A[j]

Question

我有一个类似于这个问题的问题:check if there exists a[i] = 2*a[j] in an unsorted array a?进行了一些修改。

The input is an array A[1...n] of n positive numbers sorted in increasing order.

The problem is to determine whether there is a pair of indices i and j such that A[i] = 2A[j].

Design and analyze an O(n) time in-place algorithm for this problem

如果我可以将每个元素的 double 值存储在一个辅助数据结构中并循环比较这些值与原始数组值，那么问题会很简单，但就地规范禁止这样做。我能想到的最好的是 O(nlogn)，其中对于 n 个元素中的每一个，我都对该元素的 double 进行二进制搜索，但我无法用更快的方式解决问题。

Answer 1

作为A正在增加，所以:

1. i > j
2. 如果A[i] > 2 * A[j] , (i, k)与 k <= j不是有效对
3. 如果A[i] < 2 * A[j] , (k, j)与 k <= i不是有效对

所以算法如下 python 代码:

def foo(a):
    i = 1
    j = 0
    n = len(a)

    while n > i > j:
        if a[i] == 2 * a[j]:
            print("a[{}] = 2 * a[{}]".format(i, j))
            i += 1
        elif a[i] < 2 * a[j]:
            i += 1
        else:
            j += 1
            if i == j:
                i += 1