This C++ program displays the number of occurences of a given number in an array using binary search which computes first and last occurence of the number inside array. It has a time complexity of O(Logn).

Here is the source code of the C++ program to display the number of occurences of a given number giving elements of array as input. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

`/*`

`* C++ Program to Find the Number of occurrences of a given Number using Binary Search approach`

`*/`

`#include<iostream>`

`#include<conio.h>`

using namespace std;

int first(int arr[], int low, int high, int x, int n)

`{`

if (high >= low)

`{`

int mid = (low + high) / 2;

if (( mid == 0 || x > arr[mid - 1]) && arr[mid] == x)

`{`

return mid;

`}`

else if (x > arr[mid])

`{`

return first(arr, (mid + 1), high, x, n);

`}`

`else`

`{`

return first(arr, low, (mid - 1), x, n);

`}`

`}`

return -1;

`}`

int last(int arr[], int low, int high, int x, int n)

`{`

if (high >= low)

`{`

int mid = (low + high) / 2;

if (( mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x )

`{`

return mid;

`}`

else if (x < arr[mid])

`{`

return last(arr, low, (mid - 1), x, n);

`}`

`else`

`{`

return last(arr, (mid + 1), high, x, n);

`}`

`}`

return -1;

`}`

int count(int arr[], int x, int n)

`{`

int i;

int j;

i = first(arr, 0, n - 1, x, n);

if (i == -1)

`{`

return i;

`}`

j = last(arr, i, n - 1, x, n);

return j - i + 1;

`}`

int main()

`{`

int n, i, x, arr[10];

cout<<"enter the number of elements\n";

cin>>n;

for (i = 0; i < n; i++)

`{`

cout<<"enter element\n";

cin>>arr[i];

`}`

cout<<"enter the element whose number of occurences to be found\n";

cin>>x;

int c = count(arr, x, n);

cout<<x<<" occurs "<<c<<" times "<<endl;

getch();

`}`

Output enter the number of elements 8 enter element 1 enter element 2 enter element 2 enter element 4 enter element 6 enter element 7 enter element 7 enter element 7 enter the element whose number of occurences to be found 4 4 occurs 1 times

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

If you wish to look at all C++ Programming examples, go to C++ Programs.