Count of an Element in a Sorted Array.

Problem: Given an array a1,a2,a3…an which is sorted in the non-decreasing order. Given an element e, find its number of occurence in the array.

For example: (1,1,1,2,2,3,3,3,4,4) is the given array and let the given element is 3. Its count is 3. For 4, it is 2.
One can think what is so difficult in the problem. It can be solved in more optimised way one can think of.
Method 1:
Simple, but not efficient.
Search for an element linearly. When it is encountered, then count it.
Complexity:

Method 2:
Efficient but consuming space.
First it involves preprocessing of O(n) and will space of O(n). In preprocessing, store the element and its count in another array
keeping its order. When, the element is to be found, it can be found in O(logn) using binary search alongwith its occurence.

Method 3:
Tricky, but efficient.
Use binary Search method to find leftmost and rightmost indices of the element.
Then use the formula right-left+1 to get the count.
Complexity: O(logn)

Code:
#include

#define PRINTRESULT(array,n,c)  printf(“%d%d\n”,c,getcountinsorted(array,n,c))
#define SIZE 16
int binarysearch(int *array,int n,int value)
{
int low=0,high=n-1,mid=(low+high)/2;
while(low<=high)
{
if(array[mid]==value)
return mid;
if(array[mid]
low = mid+1;
else
high = mid-1;
mid = (low+high)/2;
}
return -1;
}

int getcountinsorted(int *array,int n,int value)
{
int low,high,mid;
mid = binarysearch(array,n,value);
if(mid<0)
return 0;
int right,left;
//Search for the rightmost index
right = mid;
low = mid+1;high = n-1;
int mid1;
while(low<=high)
{
mid1 = (low+high)/2;
if(array[mid1]==value)
{right = mid1;low=mid1+1;}
else if(array[mid1]
low = mid1+1;
else
high = mid1-1;
}
//Search for the leftmost index
low=0;high = mid-1;
left=mid;
while(low<=high)
{
mid1 = (low+high)/2;
if(array[mid1]==value)
{left = mid1; high=mid1-1;}
else if(array[mid1]
low = mid1+1;
else
high = mid1-1;
}
return right-left+1;
}

/* Driver Program to test the above routine */
int main()
{
int array[SIZE] = {1,1,2,2,2,3,4,5,6,7,7,7,7,8,11,11};
PRINTRESULT(array,SIZE,1);
PRINTRESULT(array,SIZE,2);
PRINTRESULT(array,SIZE,3);
PRINTRESULT(array,SIZE,4);
PRINTRESULT(array,SIZE,5);
PRINTRESULT(array,SIZE,6);
PRINTRESULT(array,SIZE,7);
PRINTRESULT(array,SIZE,8);
PRINTRESULT(array,SIZE,9);
PRINTRESULT(array,SIZE,10);
PRINTRESULT(array,SIZE,11);
PRINTRESULT(array,SIZE,12);
return 0;
}

Output:
1 2
2 3
3 1
4 1
5 1
6 1
7 4
8 1
9 0
10 0
11 2
12 0