Find all differences in sorted array

Question

I have a sorted (ascending) array of real values, call it a (duplicates possible). I wish to find, given a range of values [x, y], all indices of values (i) for which an index j exists such that: j>i and x <= a[j]-a[i] <= y Or simply put, find values in which exists a “forward difference” within a given range.

The output is a Boolean array of length a.Length. Since the array is sorted all forward differences, x and y are positive.

The best I’ve managed to do is start from each index looking at the subarray in front of it and perform a binary search for x+a[i] and check if a[j]<=y+a[i]. I think this is O(n log n). Is there a better approach? Or something I can do to speed things up.

I should note that eventually I want to perform the search for many such ranges [x,y] over the same array a, but the number of ranges is very much smaller than the length of the array (4-6 orders of magnitude smaller) - therefore I’m far more concerned with the complexity of the search.

Example:

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

with range x,y=[99,101] should return:

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

For only values 0,1 and 185 have a forward difference within the range.

Code from memory, might have some bugs:

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;
    }
}

Thanks!

Masakomasan

can you add a single example array and range? – Storm

The best I’ve managed to do - Could you show your attempt? This is an interesting question and I would hate to see it closed due to lack of code in the question. – Beaulahbeaulieu

@Beaulahbeaulieu I added my attempt – Masakomasan

Answer 1

As long as the input array is sorted, there is a linear solution to the problem. The key is to use two indexes to traverse of the array a.

bool[] findDiffs(int[] a, int x, int y)
{
  bool[] result = new boolean[a.Length];
  int j = 0;

  for (int i = 0; i < a.Length; ++i) {
    while (j < a.Length && a[j] - a[i] < x) {
      ++j;
    }
    if (j < a.Length) {
      result[i] = a[j] - a[i] <= y;
    }
  }

  return result;
}

With a = [0,100,1000,1100] and (x,y) = (99,100):

i = 0, j = 0 => a[j] - a[i] = 0 < x=99     => ++j
i = 0, j = 1 => a[j] - a[i] = 100 <= y=100 => result[i] = true; ++i
i = 1, j = 1 => a[j] - a[i] = 0 < x=99     => ++j
i = 1, j = 2 => a[j] - a[i] = 900 > y=100  => result[i] = false; ++i
i = 2, j = 2 => a[j] - a[i] = 0 <= x=99    => ++j
i = 2, j = 3 => a[j] - a[i] = 100 <= y=100 => result[i] = true; ++i
i = 3, j = 3 => a[j] - a[i] = 0 <= x=99    => exit loop

Bookseller

Answer 2

Make two indexes left and right and walk through array. Right index moves until it goes out of range for current left one, then check whether previous element is in range. Indexes move only forward, so algorithm is linear

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

Another point of view on this algorithm:
-while difference is too low, increment right
-while difference is too high, increment left

Verine