See the original problem on HackerRank.
Solutions
The linear solution is simple: just count the frequencies of both negative and positive integers.
However, the optimal solution is more interesting: leveraging the sorted nature of the array, we can exploit binary search. Here’s where a crucial detail comes into play: 0
is neither positive nor negative. Consequently, searching for 0
presents us with an opportunity to swiftly determine the count of positive and negative integers.
In essence, we need to recall two fundamental concepts regarding binary searches:
 Lower bound: locates a specified element or the next one if the specified element is absent;
 Upper bound: locates the next element after the specified one.
Clearly, both are binary searches, operating in logarithmic time.
The idea here is to find both lower bound and upper bound of 0
:
 all the elements before the lower bound of
0
are necessarily negative (lower bound of0
finds either0
or the first positive);  all the elements after the upper bound of
0
are necessarily positive (upper bound of0
finds the first positive).
For example:


lower bound(0)=3
, indeed the number of negative integers is30=3
upper bound(0)=4
, indeed the number of positive integers is54=1
Another example without 0
:


lower bound(0)=3
, indeed the number of negative integers is still30=3
upper bound(0)=4
, indeed the number of positive integers is still43=1
Another example with more 0
:


lower bound(0)=2
, indeed the number of negative integers is20=2
upper bound(0)=5
, indeed the number of positive integers is105=5
The most concise C++ code is here below:


equal_range
combines both lower_bound
and upper_bound
into a single function call.
In Python, for example, we explicitly call both:

