list manipulation - Fast way of finding position of Interval containing an Integer

I have a large list (about 2.2 million) of pairs of integers. Each pair defines an Interval[{}]. Given some integer x, I need to find the position of the interval in my list that bounds x (or alternatively, return the element of the list).

None of the intervals overlap, thus x can belong to only one of the intervals. You can assume the large list is sorted. The challenge is that I need to run this "look-up" millions of times, so even a small gain in speed would be very beneficial

I tried a few obvious brute force approaches. First I created a list of intervals from the list of integer pairs, and then tried

Pick[myBigList, 
     Map[IntervalMemberQ[#, x] &, myBigList]]; //AbsoluteTiming

4.196432

and then

Select[myBigList, IntervalMemberQ[#,x]& ]; // AbsoluteTiming

8.814063

Assuming the list is ordered, then

LengthWhile[mySortedBigList, #[[1]] <= x &]

3.556826

All of these methods seem too slow. Any suggestions would be much appreciated.

(For those of you interested, here's the background on this problem. I need a fast way of translating an IP address to an approximate set of latitude-longitude coordinates. Each pair of integers in the list above corresponds to a range of IP addresses that have been converted from the zz.zz.zz.zz format to an integer. The interval defined by each pair of integers is associated with a set of lat-long coordinates. Again, this needs to be run millions or tens of millions of time on a regular basis. When this look-up was done on a 64-bit Windows desktop system running standard SQL, it took about 8 hours to geocode ten million IPs)

Thanks,

Mark