Why Dual Sorting Works

When $p < \text{mid}$, all center intervals contain mid, so they extend at least to mid. You only need to check if they extend left far enough to reach $p$.

By sorting center intervals by low endpoint, you scan from smallest low upward.

Once we hit an interval with $\text{low} > p$, all remaining intervals also have $\text{low} > p$ (sorted order), so you stop.

Similarly, when $p > \text{mid}$, you sort by high endpoint and scan from largest high downward.

This scanning trick is why we get $O(\log n + k)$ instead of $O(\log n \cdot m)$ where $m$ is the number of center intervals. You only scan intervals that overlap.