Reputation: 1466
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!
Upvotes: 7
Views: 245
Reputation: 3036
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
Upvotes: 1
Reputation: 80187
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
Upvotes: 3