Say we need to find the number of occurence of a number k.
If k has to occur atleast n/2 times (that is half of the array size), then k must be there in the middle. There is no way that there are atleast n/2 occurences of k and k is not there in array[middle]. BUT, vice-versa is not true.
Maybe what we can do here is to first look in the condition C1: (array[middle] == k)
If C1 is False, go home.
But if C1 is True we may have something to work with.
Now the n/2 appearances of k will be like a run of k's. Because it is mentioned that we have a sorted array with us. The extremes of the run of k's is what we need to deal with.
Find any one extreme (left or right) of the run of k's. Say you find the index of left extreme(π).
Now to find this value of π we shall use the binary search. This will take T(n) = T(n/2) + 1, T(n) = O (logn).
Now if the run of k's is atleast n/2 then the right extreme must have k as well. (Here WLOG we are assuming that the run is of exactly n/2 length).
right extreme for a run of length n/2(where π is the left extreme of the run) = π+n/2.
Condition C2: ( array[π+n/2] == k)
If C2 is False, it means the run didn't last for n/2 length. Return fail.
If C2 is True, it means k has appeared at least n/2 times in the sorted array.