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?