# 1. Introduction

Given a sorted array that may contain duplicates, the task is to count occurrences of a number. Using the properties of a sorted array, we can efficiently find the count of a specific number using a binary search approach.

# 2. Program Steps

1. Define a function *binarySearch* that finds the first or last occurrence of a given number.

2. If the number is not found, return 0 occurrences.

3. If the number is found, find both the first and last occurrence of that number using binary search.

4. The difference between the indices of the last and first occurrence plus one gives the total count of that number.

# 3. Code Program

```
class CountOccurrences {
public static int binarySearch(int[] arr, int num, boolean searchFirst) {
int start = 0;
int end = arr.length - 1;
int result = -1;
while (start <= end) {
int mid = (start + end) / 2;
if (num == arr[mid]) {
result = mid;
if (searchFirst) {
end = mid - 1;
} else {
start = mid + 1;
}
} else if (num < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return result;
}
public static int countOccurrences(int[] arr, int num) {
int first = binarySearch(arr, num, true);
if (first == -1) {
return 0;
}
int last = binarySearch(arr, num, false);
return last - first + 1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 3, 3, 4};
int num = 3;
int count = countOccurrences(arr, num);
System.out.println("Number " + num + " appears " + count + " times.");
}
}
```

### Output:

Number 3 appears 3 times.

# 4. Step By Step Explanation

1. We define a modified *binarySearch* function that can be used to find either the first occurrence or the last occurrence of a number in the sorted array.

2. If we're looking for the first occurrence (*searchFirst* is true), once we find the number, we move towards the left half. If we're looking for the last occurrence, we move towards the right half.

3. *countOccurrences* function uses the *binarySearch* function to first find any occurrence of the number. If no occurrence is found, it returns 0.

4. If an occurrence is found, it then finds the first and last occurrence of the number. The total occurrences are the difference between these indices plus one.

5. In the *main* method, we test our functions with a sample sorted array containing duplicates.