Finding an interval in a binary search tree that contains a point I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare against the low and high of each interval and descend either left, right, or exit.

Is it possible to only compare against the low, or the high, or some kind of median to reduce the number of comparisons in the average case? I know the optimal lower bound would be O(lg n) but in many cases the max of a predecessor is very close to the min of a node, which seems redundant.

I'm wondering if there is a way to branch more aggressively at first and make small adjustments along the way. Potentially determining the next step based on which direction we branched previously. 

I could not find any literature on this. Interval trees don't quite match this setup and almost all other resources relate to overlapping intervals. 

What would be an optimal algorithm to find an interval?
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.