Counting the number of elements in a sorted array
I want to find a solution [whose] algorithm time complexity is lower than O(n).


You'll have to be more specific. What you asked for literally isn't possible; but sometimes people use "big-O" notation loosely, either out of laziness or because they haven't yet been exposed to the notation expressing their intended precise gradations of meaning.

Notice that if I give you the input

1 2 3 4 5 6 7 8 9 10 11 12 13 ...


then you must output

number of 1 is 1
number of 2 is 1
number of 3 is 1
number of 4 is 1
...


— that is, if the size of the input is n, then the worst-case size of the output is O(n). Printing those O(n) bytes of output will take O(n) time just by itself. Anything else the program does (besides print its output) can only make the overall program slower, not faster.

On the above worst-case input, your "repeated binary search" algorithm runs in O(n log n) time, which is worse than O(n).

Now, if you're not concerned about worst-case inputs, but merely with the average input... well, then you'd have to define a notion of "the average input". You'll have to come up with some model of what kinds of input you expect. One way to do this is to come up with an algorithm for generating inputs, and then treat it as your model. For example:

def get_random_input(n):
    return sorted([random.randrange(n) for i in xrange(n)])


Or:

def get_random_input(n):
    return sorted([random.randrange(100) for i in xrange(n)])


On these two different models, your algorithm performs very differently. On the latter, you do well: O(log n). On the former, you do poorly: O(n log n).

This is kind of like asking for a compression algorithm that compresses all possible inputs. You can get compression for some inputs only at the expense of others; the art is deciding which kinds of inputs are "interesting" and which can safely be blown up. In this case, you can get sub-O(n) performance for some inputs only at the expense of others; the art is deciding which kinds of inputs are "interesting", which is to say, deciding on a model for your "average" or "expected" input.

EDIT: My analogy above is flawed, as indicated by LinMa's comments below this answer. See, if you can get O(log n) performance on your "expected" inputs while blowing up the "unexpected" inputs by only a constant factor (e.g. "O(n) plus a constant number of comparisons" or "O(n) times two"), then you can keep your algorithm's worst-case big-O "constant" while improving the best-case.

Hope this helps!