c# - 查找排序数组中的所有差异

Question

我有一个排序(升序)的实数值数组，称它为(可能重复)。我希望在给定值范围 [x, y] 的情况下找到所有索引 j 存在的值 (i) 的索引，以便: j>我和 x <= a[j]-a[i] <= y或者简单地说，找到在给定范围内存在“前向差异”的值。

输出是一个长度为 a.Length 的 bool 数组。由于数组对所有前向差异进行排序，因此 x 和 y 为正。

我所能做的最好的事情是从每个索引开始，查看它前面的子数组，然后对 x+a[i] 执行二进制搜索，并检查是否 a[j]<=y+a[i ].我认为这是 O(n log n)。有更好的方法吗？或者我可以做些什么来加快速度。

我应该注意到，最终我想在同一个数组 a 上搜索许多这样的范围 [x,y]，但是范围的数量远小于数组的长度(4-6 个数量级)幅度更小) - 因此我更关心搜索的复杂性。

示例:

a= 0, 1, 46, 100, 185, 216, 285

范围 x,y=[99,101] 应该返回:

[true, true, false, false, true, false, false]

只有值 0,1 和 185 在范围内具有前向差异。

内存中的代码，可能有一些错误:

int bin_search_closesmaller(int arr[], int key, int low, int high)
{
    if (low > high) return high;
    int mid = (high - low)/2;
    if (arr[mid] > key) return bin_search_closesmaller(arr, key, low, mid - 1);
    if (arr[mid] < key) return bin_search_closesmaller(arr, key, mid + 1, high);
    return mid;
}

bool[] findDiffs(int[] a, int x, int y)
{
    bool[] result = new bool[a.Length];
    for(int i=0; i<a.Length-1;i++)
    {
        int idx=bin_search_closesmaller(a, y+a[i], i+1, a.Length-1);
        if (idx==-1) continue;
        if (a[idx]-a[i] >= x) result[i]=true;
    }
}

谢谢!

Answer 1

创建两个索引 left 和 right 并遍历数组。 Right 索引移动到当前 left 索引超出范围，然后检查前一个元素是否在范围内。索引只向前移动，所以算法是线性的

 right=2
 for left = 0 to n-1:
    while A[right] < A[left] + MaxRangeValue
       right++
    Result[left] =  (A[right - 1] <= A[left] + MinRangeValue)

关于这个算法的另一种观点:
-当差异太小时，向右增加
-当差异太大时，向左增加