# 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?

• what do you mean by "the average case"? If your algorithm is based on some sequence of comparisons, then the leaves of the decision tree represent your answers, and there is a lower bound of $\log(n)$ on the number of comparisons – lox Apr 16 '19 at 17:08
• The most common / expected result. I'm wondering whether in some cases I can avoid comparison based on the path taken. For example, compare to the low to go left (or exit) or otherwise go right, then compare to the high of the right to go right or fall back to comparing to the min or the parent. My intuition is suggesting a contextual search is possible but I have not figured out how they might work. – rtheunissen Apr 16 '19 at 18:35

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 < q$$ and the right child the same for $$x>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 ($$=, <, >)$$

$$\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.

• Improving the complexity is not possible, of course. I'm hoping to improve the constant, if possible. You say that q is a median, but what if the point is less than q but greater than i, ie. belongs to the current segment but the decision based on the median would be to go left, exiting what is actually the correct interval. – rtheunissen Apr 20 '19 at 18:03
• if the median $q$ belongs to some segment $(i,j)$, you can always add the query "does $x \geq i$ and $x \leq j$?". It is tantamount to coincidentally having $x = q$ – lox Apr 20 '19 at 18:29