## Problem Statement

Given a sorted array of integers and a `target` element. Find the number of occurrences of the `target` in the array. You must write an algorithm with `O(log n)` runtime complexity.

Example 1:

``````Input: a[] = {1, 1, 2, 2, 2, 2, 3},  target = 2
Output: 4 (2 appears four times in the array)``````

Example 2:

``````Input: a[] = {1, 1, 2, 2, 2, 2, 3},  target = 1
Output: 2 (1 appears twice in the array)``````

Example 3:

``````Input: a[] = {1, 1, 2, 2, 2, 2, 3},  target = 4

## Binary Search to find the count (frequency) of an element in a sorted array

This problem is a variation of the problem Find the First and Last Position of an Element in a Sorted Array. If we can find the first and last position of the target element in the array, then we can easily find the count which will be equal to `lastPosition - firstPosition + 1`

Let’s look at the implementation

``````import java.util.Scanner;

class CountOfElementInSortedArray {
private static int binarySearchFirstPosition(int[] a, int target) {
int start = 0;
int end = a.length-1;

int firstPosition = -1;

while(start <= end) {
int mid = (start + end)/2;

if(target == a[mid]) {
// Found target, update firstPosition and move to the left to find a smaller position by setting end=mid-1
firstPosition = mid;
end = mid-1;
} else if (target < a[mid]) {
end = mid-1;
} else {
start = mid+1;
}
}

return firstPosition;
}

private static int binarySearchLastPosition(int[] a, int target) {
int start = 0;
int end = a.length-1;

int lastPosition = -1;
while(start <= end) {
int mid = (start + end)/2;

if(target == a[mid]) {
// Found target, update lastPosition and move to the right to find a higher position by setting start=mid+1
lastPosition = mid;
start = mid+1;
} else if (target < a[mid]) {
end = mid-1;
} else {
start = mid+1;
}
}

return lastPosition;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = keyboard.nextInt();
}
int target = keyboard.nextInt();
keyboard.close();

int firstPosition = binarySearchFirstPosition(a, target);
int lastPosition = binarySearchLastPosition(a, target);

if(firstPosition != -1 && lastPosition != -1) {
System.out.printf("Count(%d) = %d%n", target, lastPosition-firstPosition+1);
} else {
System.out.printf("Count(%d) = 0%n", target);
}
}
}``````
``````# Output
\$ javac CountOfElementInSortedArray.java
\$ java CountOfElementInSortedArray
7
1 1 2 2 2 2 3
2
Count(2) = 4

\$ java CountOfElementInSortedArray
7
1 1 2 2 2 2 3
1
Count(1) = 2

\$ java CountOfElementInSortedArray
7
1 1 2 2 2 2 3
4
Count(4) = 0``````