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.