mapping subintervals

[Lee Sander]

hi,
I have the following problem which is turning out to be non-trivial. I
realize that this is not
exactly a python problem but more of an algorithm problem -- but I
post it here because
I want to implement this in python.

I want to write a code that given an interval (integer tuple:
start,stop) will find which other
interval it matches to. Here is an example,
suppose I have the following NON-OVERLAPPING intervals

10 - 21   ==> 'a1'
34 - 51   ==> 'a2'
77 - 101 ==> 'a3'
etc

So, suppose I'm give an interval such as (42,50), I should go through
the list and map it to "a2" etc
if the region is a subset of an exiting interval.  If the query
interval does not exist in the table or
maps to two or more intervals (eg, (45, 80)) the program return a
None.

One naive way to solve this problem is to create an array such as
follows:
[None, None, None, ...., None, a1, a1, a1, ..., a1, None, None ...,
None, a2, ... etc] at indicies
  1        2        3              9       10  11  12       21
22      23          33     34, ...

now with this in place I can easily solve the problem. However, this
is not a feasable solution
because the initial list has intervals whose range can go to billions!
So I need a smarter
idea. So what I can do is sort the initial list and then go through
each element from the start
and test if the  a > X[i][0] and b < X[i][1]
where (a,b) is my query start and stop
and X is a n x 2 array with the known intervals.
I don't like this solution because it can be really really slow as for
each query I'm doing a
linear search and on average I'll be searching almost half the list
before I find the right
interval.
Is there a smarter way to do this?
I've my problem is not clear please let me know and I'll try to
explain the unclear parts again.
Many thanks
Lee