Count the Number of Occurrences of an Element in a Sorted Array - Java Solution

1. Introduction

In this blog post, we'll solve the problem that involves finding the frequency of an element in a sorted array. This is a common problem in search algorithms, and the goal is to achieve an efficient solution with O(log n) runtime complexity using binary search.

Problem

Given a sorted array of integers and a target element, find the number of occurrences of the target in the array.

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
Output: 0 (4 is not found in the array)

2. Solution Steps

1. Use binary search to find the first occurrence of the target element.

2. Use binary search to find the last occurrence of the target element.

3. The frequency of the target is the difference between the indices of the last and first occurrences plus one.

4. If the target is not found, return 0.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a = {1, 1, 2, 2, 2, 2, 3};
        System.out.println("Frequency of 2: " + findFrequency(a, 2));
        System.out.println("Frequency of 1: " + findFrequency(a, 1));
        System.out.println("Frequency of 4: " + findFrequency(a, 4));
    }

    // Method to find the frequency of a target element
    public static int findFrequency(int[] a, int target) {
        int firstOccurrence = findFirstOrLastOccurrence(a, target, true);
        if (firstOccurrence == -1) return 0; // Target not found

        int lastOccurrence = findFirstOrLastOccurrence(a, target, false);
        return lastOccurrence - firstOccurrence + 1;
    }

    // Helper method to find the first or last occurrence of a target
    private static int findFirstOrLastOccurrence(int[] a, int target, boolean findFirst) {
        int start = 0, end = a.length - 1, ans = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (a[mid] == target) {
                ans = mid;
                if (findFirst) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else if (a[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ans;
    }
}

Output:

Frequency of 2: 4
Frequency of 1: 2
Frequency of 4: 0

Explanation:

The findFrequency method first finds the first and last occurrences of the target element in the sorted array using modified binary search. 

The frequency of the target element is then calculated as the difference between these indices plus one. For example, for the input array [1, 1, 2, 2, 2, 2, 3] and target 2, the method finds that 2 appears first at index 2 and last at index 5, so it appears 4 times.