## In the given sorted array, find the number of times X is coming. (X is integer)

### Example

input array: [1,2,2,2,2,3,3,3,4,4,4,5,5]

occurrences of 1 here output : 1

occurrences of 2 here output : 4

occurrences of 3 here output : 3

occurrences of 4 here output : 3

occurrences of 5 here output : 2

## ALGORITHM 1

**TIME COMPLEXITY – O(logN)**

**SPACE COMPLEXITY – O(1)**

**1.** Simply do a modified binary search such that

**2.** Find the first occurrence of X like this:

- Check if the middle element of the array is equal to X.
- If equal or greater element is at mid then reduce the partition from start to mid-1. As we will have the first occurrence in the left side of mid of array then.
- If the middle element is smaller then we will check in the right side of middle element as the array is sorted.
- Return the first occurrence.

**3.** Now similarly find the last occurrence of X in the array by doing

- Check if the middle element of the array is equal to X
- If equal or smaller element is at mid then increase the partition from mid+1 to high. As we will have the last occurrence in the right side of mid of array then.
- Else search in left side of array
- return the last occurrence

**4.** Now the number of occurrences is simply last occurrence – first occurrence.

### Algorithm 1 Working Example

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {1,2,2,3,3,3,4,5,8,8,8,8,9};//array
int N = sizeof(arr)/sizeof(arr[0]); // size of array
int X; // number whose count is to be found out
cin >> X;
int count = 0; //initially its count is zero
for(int i = 0 ; i < N; i++)
if(arr[i] == X)
count++;
cout<<count;
return 0;
}
```

## ALGORITHM 2

**TIME COMPLEXITY – O(logN)**

**SPACE COMPLEXITY – O(1)**

- Simply do the same approach as algorithm 1 but using upper_bound() and lower_bound functions.
- Calculate the last occurrence using upper_bound() and first occurrence via lower_bound() functions.
- Number of occurrences is simply the index obtained by upper_bound() –
- lower_bound().

Low_bound(), Upper_bound are STL functions. Standard Template Library (STL)

### Algorithm 2 Working Example

**Input array**

Lower_bound(5, input array) = 3

Upper_bound(5, input array) = 6

Therefore,

Total number of occurrences of 5 = Upper_bound – Lower_bound

= 6 – 3

= 3.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {1,2,2,3,3,3,4,5,8,8,8,8,9};//array
int N = sizeof(arr)/sizeof(arr[0]); // size of array
int X; // number whose count is to be found out
cin >> X;
int count = 0; //initially its count is zero
count = upper_bound(arr,arr+N,X) - lower_bound(arr,arr+N,X); //last occurence - first occurence is the count
cout<<count;
return 0;
}
```

## ALGORITHM 3

**TIME COMPLEXITY – O(N)**

**SPACE COMPLEXITY – O(1)**

- Simply run a loop.
- If we get an element equal to X start increasing the count
- Till we see X increase the count and as soon as we get a number different from X then we display the obtained count as it is a sorted array.

### Algorithm 3 Working Example

Loop Ends here because, element other than 5 came and there cannot be any other occurrences of 5 in the array.

Therefore,

Total number of occurrences of 5 in the given array is count = 3.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
int first_occurence(int arr[],int N,int X)
{
int low = 0 , high = N-1;
int first = INT_MAX;
while(low <= high)
{
int mid = low + ((high-low)>>1);
if(arr[mid] == X) //if found then check the left part for further occurence
{
if(mid < first)
first = mid;
high = mid-1;
}
else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
low = mid + 1;
else if (arr[mid] > X)//if middle element is larger than X check in left subpart
high = mid - 1;
}
return first;
}
int last_occurence(int arr[],int N,int X)
{
int low = 0 , high = N-1;
int last = INT_MIN;
while(low <= high)
{
int mid = low + ((high-low)>>1);
if(arr[mid] == X) //if found check in right subpart for last occurence
{
if(mid > last)
last = mid;
low = mid+1;
}
else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
low = mid + 1;
else if (arr[mid] > X)//if middle element is larger than X check in left subpart
high = mid - 1;
}
return last;
}
int main()
{
int arr[] = {1,2,2,3,3,3,4,5,8,8,8,8,9};//array
int N = sizeof(arr)/sizeof(arr[0]); // size of array
int X; // number whose count is to be found out
cin >> X;
int count = 0; //initially its count is zero
int last = last_occurence(arr,N,X);
if(last != INT_MIN)
count += last;
int first = first_occurence(arr,N,X);
if(first != INT_MAX)
count -= first;
cout<<first<<endl;
cout<<last<<endl;
cout<<count;
return 0;
}
```

Normal

0

false

false

false

EN-US

X-NONE

X-NONE