So I have an array of distinct pairs of positive integers. That is, my array looks something like this (for instance):
{ (1,5) , (6,4), (5,3), (2,3), (2,4) }
And my task is, for a given pair (a,b) find (if it exists) the pair (c,d) which has c > a and d > b and, in addition, is the “minimal” such pair (that is, c is minimal and, if there are multiple pairs which satisfy this with the same c, then d is minimal).
So for instance, if I run the query for the above array for pair (1,1), it should return (2,3) and if I feed it (5,2) it should return (6,4).
Now the problem is that I have to run multiple queries so linear time is not good enough. And my question is: is there any way in / any law by which I can “sort” such an array so that I can later run binary searches on it to find my answer?
I was thinking I could simply go like this: let (x1,y1) and (x2,y2) be two pairs to compare. Then:
if(x1<x2)
//pair 1 is smaller
else if(x1==x2 && y1<y2)
//pair 1 is smaller
else
//pair 2 is smaller
This seemed to solve most cases, however.. if I have an array which looks like this:
{ .... (50,60) ..... }
where (50, 60) is at the middle of the array. And I run a query for (40,70) for instance. The problem is that the pair that I want to find could be either on the left or on the right of (50,60) (we could have something like (45,90) on the right of (50, 60), but then again we could only have (x,10) on the left of (50,60) where x<50 so no pair on the left would satisfy our condition and I’d have to look to the right).
So to sum it up, if I’m running a query for pair (x1,y1) and through my binary search I come across and element (x2,y2) which has x1<x2 and y1>=y2, then my algorithm cannot decide whether it should keep searching left or right. So I have to search both sides and in a worst case scenario this ends up being O(n).
So is there a more clever way in which you can do this? Any help would be appreciated. Thanks in advance 🙂
Without using any extra storage, I think the best you can do is a binary search on the first element, then linear search forward from there to match the second element. This has O(n) worst case performance, but should be close to O(log n) in the average case, especially since you only need to search this way after hitting an ambiguous direction.
If you have sufficient storage and the time to do the precalculation, you could make a two-dimensional pre-sorted data structure, like the following for your example { (1,5) , (6,4), (5,3), (2,3), (2,4) }:
[(1, [(2,3), (5,3), (2,4), (6,4), (1,5)]),
(2, [(2,3), (5,3), (2,4), (6,4)]),
(5, [(5,3), (6,4)]),
(6, [(6,4)])]
Then just do a binary search for the 1, 2, 5, or 6 as the first element, which gives you a list sorted by the second element, where you can do another binary search. This is O(n2) for space, but gives you O(log n) in runtime.
1