Binary Search

Count the number of occurrences (frequency) of an element in a sorted array

Rajeev SinghAlgorithms1 mins read

Count the number of occurrences (frequency) of an element in a sorted array

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

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