Write your own lower bound and upper bound functions instead of searching for a target value alone in your binary search. Also, notice that you’ve used binary search only on rhs, so you don’t need to sort lhs. This can save you good time.
In case you have to use a single value search, you can replace it with lower-bound search as well with almost similar runtime performance.
Also, when you have to calculate both the upper bound and lower bound using STL, prefer using equal_range function.
I had my solution accepted with and without STL so I can tell you the constraints are lenient enough.
