Finding an interval in a binary search tree that contains a point
You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below).

What you can do is some minor optimizations; if each node in your tree saves the end of the rightmost segment and the beginning of the leftmost segment, by adding $2$ comparisons to each query, you can immediately decide $x$ is outside any segments when it becomes out of bounds. These comparisons do not increase your overall complexity, but they also don't improve it.



Let us consider the data as $n$ disjoint line segments. Or to be formal, $I = \{(i_1,j_1),\dots (i_n,j_n) \} $

Suppose given a query $x$ we wish to determine in which interval $(i_t,j_t)$ our query $x$ is located at, or whether no $ 0 \leq k \leq n$ exists s.t $x \in (i_k,j_k)$. 

Since your algorithm performs comparisons, it can be represented as a decision tree; a node represents a comparison $x : q$; the left child are the comparisons you would make if $x &lt; q$ and the right child the same for $x&gt;q$. 

Note that since in your case, your values $q$ are medians, if $x=q$ you can finish your algorithm (and $x$ belongs to that segment).

Let's denote the decision tree $T$.

Some observations about $T$:

$\bullet$ $T$ MUST have at least $n+1$ unique leaves; one for each segment $(i_t, j_t)$ and one that represents the decision that $x$ belongs to no segment.

$\bullet$ Each inner node $v$ of $T$ has three children ($=, &lt;, &gt;)$

$\bullet$ A trenary tree of height $h$ has at most $3^h$ leaves; 
$3^h \geq n+1 \rightarrow h \geq \log_3{(n+1)} \geq \log_3{n}$ 

Since $\log_3{n} = \Omega(\log n)$, we proved a lower bound for comparison based search, and thus any search as described by your algorithm must perform at least $\log n$ queries.