# Count Occurrences in Sorted Array

Problem Statement: You are given a sorted array containing N integers and a number X, you have to find the occurrences of X in the given array.

Examples:

```Example 1:
Input: N = 7,  X = 3 , array[] = {2, 2 , 3 , 3 , 3 , 3 , 4}
Output: 4
Explanation: 3 is occurring 4 times in
the given array so it is our answer.

Example 2:
Input: N = 8,  X = 2 , array[] = {1, 1, 2, 2, 2, 2, 2, 3}
Output: 5
Explanation: 2 is occurring 5 times in the given array so it is our answer.```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Solution 1: Using linear search

Approach:

The approach is simple. We will linearly search the entire array, and try to increase the counter whenever we get the target value in the array. Using a for loop that runs from 0 to n – 1, containing an if the condition that checks whether the value at that index equals target. If true then increase the counter, at last return the counter.

Code:

## C++ Code

``````#include <iostream>

using namespace std;

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

int k = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
k++;
}
}
return k;
}

int main() {
int n = 7;
int x = 3;
int arr[] = {2,2,3,3,3,3,4};
int ans = count(arr, n, x);
cout <<x<<" occurs "<<ans<<" times in the array" << endl;
}
``````

Output: 3 occurs 4 times in the array

Time Complexity: O(N)

Space Complexity: O(1)

## Java Code

``````import java.io.*;

class TUF {

public static int count(int[] arr, int n, int x) {
int k = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x) {
k++;
}
}
return k;

}

public static void main(String[] args) {
int n = 7;
int x = 3;
int[] arr = {2,2,3,3,3,3,4};

int ans = count(arr, n, x);
System.out.println(x+" occurs "+ans+" times in the array");
}
}
``````

Output: 3 occurs 4 times in the array

Time Complexity: O(N)

Space Complexity: O(1)

### Solution 2: Using Binary  search

Approach: This approach uses Binary Search to find the index of the X. Then checks the left and right half of the array for getting more occurrences of X.

Call a function that uses Binary search to determine the index of the X in the array, and return the index.

Now we must check for the first occurrences of X at the left and right half of the array.

Increase the counter if X exists at the left and right half of the array. At last return the counter.

Code:

## C++ Code

``````#include <iostream>

#include <iostream>

using namespace std;

int binary(int arr[], int n, int x) {
int s = 0;
int e = n - 1;

while (s <= e) {
int m = (s + e) / 2;

if (arr[m] == x) {
return m;
} else if (arr[m] < x) {
s = m + 1;
} else {
e = m - 1;
}
}
return -1;
}

int count(int arr[], int n, int x) {
// code here
// get the index of X in array
int idx = binary(arr, n, x);

// if X does not exist return 0;
if (idx == -1) {
return 0;
}

int k = 1;
int left = idx - 1;

// check left half for X
while (left >= 0 && arr[left] == x) {
k++;
left--;
}
// check right half for X
int right = idx + 1;
while (right < n && arr[right] == x) {
k++;
right++;
}

return k;
}

int main() {
int n = 7;
int x = 3;
int arr[] = {2,2,3,3,3,3,4};

int ans = count(arr, n, x);
cout <<x<<" occurs "<<ans<<" times in the array" << endl;
}
``````

Output: 3 occurs 4 times in the array

Time Complexity: O(logN)

Space Complexity: O(1)

## Java Code

``````import java.io.*;

class TUF {
public static int binary(int[] arr, int n, int x) {

int s = 0;
int e = arr.length - 1;

while (s <= e) {
int m = (s + e) / 2;

if (arr[m] == x) {
return m;
} else if (arr[m] < x) {
s = m + 1;
} else {
e = m - 1;
}
}
return -1;

}
public static int count(int[] arr, int n, int x) {

// code here
// get the index of X in array
int idx = binary(arr, n, x);

// if X does not exist return 0;
if (idx == -1) {
return 0;
}

int k = 1;
int left = idx - 1;

// check left half for X
while (left >= 0 && arr[left] == x) {
k++;
left--;
}
// check right half for X
int right = idx + 1;
while (right < n && arr[right] == x) {
k++;
right++;
}

return k;

}

public static void main(String[] args) {
int n = 7;
int x = 3;
int[] arr = {2,2,3,3,3,3,4};

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

System.out.println(x+" occurs "+ans+" times in the array");
}
}
``````

Output: 3 occurs 4 times in the array

Time Complexity: O(logN)

Space Complexity: O(1)

Special thanks to Rushikesh Yadav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article