Count Occurrences - C++ Solution

1. Introduction

This blog post delves into a common problem in array processing - counting the occurrences of a given number in a sorted array. This is a fundamental problem in search algorithms, especially when dealing with datasets containing duplicates.

Problem

Given a sorted array of integers which may contain duplicates, the objective is to return the count of occurrences of a specified target number in the array.

2. Solution Steps

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

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

3. The count of occurrences is the difference between these indices, plus one.

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

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the first occurrence of the target
int findFirst(const vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1, res = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            res = mid;
            high = mid - 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

// Function to find the last occurrence of the target
int findLast(const vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1, res = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            res = mid;
            low = mid + 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

// Function to count occurrences of the target
int countOccurrences(const vector<int>& nums, int target) {
    int first = findFirst(nums, target);
    if (first == -1) return 0; // Target not found
    int last = findLast(nums, target);
    return last - first + 1;
}

int main() {
    vector<int> nums = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9};
    int target = 5;
    cout << "Count of " << target << ": " << countOccurrences(nums, target) << endl;
    return 0;
}

Output:

Count of 5: 3

Explanation:

The program uses binary search to find the first and last occurrences of the target number in the sorted array. The difference between these indices, plus one, gives the total count of occurrences. For instance, in the array [2, 5, 5, 5, 6, 6, 8, 9, 9, 9] with target 5, the count is 3 as 5 appears three times. Similarly, for target 6, the count is 2. If the target is not present, like 6 in the array [5, 4, 3, 2, 1], the count is 0.