Approach to finding the number of occurrences(using binary search)
We can use binary search to find the number of occurrences in a sorted array.This is a better approach and a very common application of binary search.
Implementation in C++
#include<iostream>
using namespace std;
int binarySearch(int a[], int l, int r, int x)
{
if (r < l)
return 1;
int mid = l + (r  l) / 2;
if (a[mid] == x)
return mid;
if (a[mid] > x)
return binarySearch(a, l, mid  1, x);
return binarySearch(a, mid + 1, r, x);
}
int countOccurrences(int a[], int n, int x)
{
int ind = binarySearch(a, 0, n  1, x);
if (ind == 1)
return 0;
int count = 1;
int left = ind  1;
while (left >= 0 && a[left] == x)
count++, left;
int right = ind + 1;
while (right < n && a[right] == x)
count++, right++;
return count;
}
// Driver code
int main()
{
int a[] = { 4,5,6,6,9,9,11,11,11,13,13};
int n = sizeof(a) / sizeof(a[0]);
int x = 11;
cout << countOccurrences(a, n, x);
return 0;
}
Output:
3
Complexity Analysis
Time complexity: O(log n+count)
Space complexity: O(n)
Also Read  Selection Sort in C
Approach to finding the number of occurrences(using improved binary search)
This is the best approach to find the number of occurrences.The approach to this method is simple:
 In this method, first we will get the index of the first occurrence of the number in array[] using binary search.Let its index be x.
 Now we will find the index of last occurrence of the number in array[] using binary search method.Let this be denoted by y
 So number of occurrences will be yx+1.
Implementation in C++
# include <bits/stdc++.h>
using namespace std;
int count(int a[], int x, int n)
{
int *low = lower_bound(a, a+n, x);
if (low == (a + n)  *low != x)
return 0;
int *high = upper_bound(low, a+n, x);
return high  low;
}
int main()
{
int a[] = {2,5,6,6,7,8,9,9,9,10,11};
int x = 9;
int n = sizeof(a)/sizeof(a[0]);
int c = count(a, x, n);
cout<<x<<" occurs "<<c <<" times in the array"<<endl;
return 0;
}
Output:
9 occurs 3 times in the array
You can try by yourself with the help of online C++ Compiler.
Complexity Analysis
Time complexity: O(log n)
Space complexity:O(n)
Also Read  Strong number in c
Frequently Asked Questions

What is sizeof() function in c++?
It is a function that returns the size of a data type like an array, expression, etc., in c++.for an array, it will return the number of elements in that array.

Name some sorting techniques used in c++?
Some of the most used sorting techniques are:
→ Bubble sort
→ Selection sort
→ Quick sort
→ Merge sort
→ Heap sort
→ Shell sort
→ Insertion sort

What is a class in c++?
A class defines a datatype, and provide set of operations, and databits.Its is also used in c language .
Conclusion
In this blog, we discussed how to find the number of occurrences in a sorted array. We then looked at linear search and binary search approach to this problem. We discussed time complexity and space complexity of this problem.We hope that this blog has helped you enhance your knowledge regarding program to count number of occurrences in a sorted array and if you would like to learn more, check out our articles on C++.
Recommended problems 
Also read  Decimal to Binary c++
Do upvote our blog to help other ninjas grow. Happy Coding!”