Find all intervals [s,e] where s,e in N_0 and s < e that overlap with another given interval

Find all intervals [s,e] where s,e in N_0 and s < e that overlap with
another given interval

I have an algorithmic problem where I would like to see if it can be
solved in better than O(n):
I have given a table T of n elements where each element is a tuple (s_i,
e_i) with s_i, e_i in N and s_i < e_i, i.e. each tuple is some kind of an
interval. I have to find all intervals that overlap with a given interval
[t0, t1] with t0, t1 in N and t0 < t1. Further, I have available two
sorted lists S and E, containing the s values, or e values respectively,
together with the index i pointing to the respective entry in T. The lists
are sorted by s values, or e values respectively. (Let's assume both, s
and e values, are unique.)
Problem:
We have to find each interval/tuple (s_i, e_i) in T where s_i <= t1 and
e_i >= t0.
My thoughts so far:
We can exclude some elements by either applying one of the interval
boundaries, i.e. searching t1 in S or t0 in E. This gives us a list L of
remaining elements:
L <- {e in E | e >= t0} or L <- {s in S | s <= t1}
However, there is no guarantee on the number of elements in L, no matter
which search we perform. Further, we have to check every element in L if s
<= t1, or e >= t0 respectively depending on which search we performed
before.
The complexity for this solution is O(n).
However, let's say that k is the maximum number of elements overlapping
with interval [t0, t1]. If we assume k << n, then the complexity is O(n/2)
since we can exclude at least n/2 elements by choosing the appropriate
search for L. Still O(n/2) is in O(n).
Can you think of a better approach to solve this problem?
(Please feel free to improve this question. Maybe it's not very clear.
Thanks)