C++ :: Binary Searching By A Key Containing Two Variables?

So I have an array of distinct pairs of natural numbers. 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).