Finding a segment which has equal number of segments before and after it
Here is an algorithm that achieves $O(n\log n)$ complexity without any elaborate data structures. Just a simple sort and a couple of loops.


Sort all the $\{a_i,b_i\}$ together. Call the resulting sequence $(x_1,\ldots,x_{2n})$.
Set $n_a\gets0$, $n_b\gets0$.
Loop for $n_b$: For $t$ going from $1$ to $2n$ do:


If $x_t=b_i$ for some $i$, increment $n_b$
Else if $x_t=a_j$ for some $j$, set $L_j\gets n_b$

Loop for $n_a$: For $t$ going from $2n$ down to $1$ do:


If $x_t=a_i$ for some $i$, increment $n_a$
Else if $x_t=b_j$ for some $j$, set $R_j\gets n_a$

Now for each interval $[a_i,b_i]$, $L_i$ and $R_i$ contain the number of intervals to its left and to its right, respectively
Final loop: For $i$ going from $1$ to $n$


If $L_i=R_i$, return $i$

Found nothing: Return null.


You might need to make some additional checks to take care of cases where $a_i=b_j$ for $i\not=j$.

Note that equality checks of the form $x_t=b_i$ can be done by saving the sorting indices. In other words, if you sort an array $u$ into another array $v$, you can save indices $\pi_t$ such that $u_t=v_{\pi_t}$.