Find all the differences in a sorted array

Question

I have a sorted (increasing) array of real values, name it (duplication is possible). I want to find, given the range of values ​​[x, y], all indexes of values ​​(i) for which there is an index j such that: j> i and x <= a [j] -a [i] <= y Or just put, find the values ​​in which there is a “forward difference” in the given range.

The output is a logical array of length a.Length. Since the array is sorted in all different directions, x and y are positive.

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

I should note that in the end I want to search for many such ranges [x, y] in the same array a, but the number of ranges is much less than the length of the array (4-6 orders of magnitude less), so Im much more interested the complexity of the search.

Example:

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

with the range x, y = [99,101] should be returned:

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

For values ​​of 0.1 and 185 only, is there a forward difference within the range.

Code from memory may have some errors:

 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!

Answer 1

While the input array is sorted, there is a linear solution to the problem. The key is to use two indexes to move 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 

Answer 2

Make two indexes left and right and go through the array. right index moves until it is out of range for the current left one, and then check if the previous item is in the range. Indexes move only forward, so the 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 the difference is too low, increment to the right
while the difference is too high, increment to the left