Count Occurrences of Element in Sorted Array in DSA C++

Mental Model

In a sorted array, all occurrences of a number are next to each other. We find where the number starts and ends to count how many times it appears.

Analogy: Imagine a row of identical books on a shelf sorted by title. To count how many copies of one title there are, find the first copy and the last copy, then count all in between.

Array: [1, 2, 2, 2, 3, 4, 5]
Indexes:  0  1  2  3  4  5  6
Target: 2
First occurrence at index 1 -> 2 -> 2 -> 2 ← last occurrence at index 3

Dry Run Walkthrough

Input: array: [1, 2, 2, 2, 3, 4, 5], target: 2

Goal: Find how many times 2 appears in the array

Step 1: Find first occurrence of 2 using binary search

mid at index 3 (value 2), move left to find first occurrence
Array: 1 -> 2 -> 2 -> [2] -> 3 -> 4 -> 5

Why: We want the earliest index where 2 appears

Step 2: Adjust search to left half, mid at index 1 (value 2), check if it's first occurrence

mid at index 1 (value 2), previous index 0 is 1 (not 2), so index 1 is first occurrence
Array: 1 -> [2] -> 2 -> 2 -> 3 -> 4 -> 5

Why: Found first occurrence because previous element is different

Step 3: Find last occurrence of 2 using binary search

mid at index 3 (value 2), check if next index 4 is 3 (not 2), so index 3 is last occurrence
Array: 1 -> 2 -> 2 -> [2] -> 3 -> 4 -> 5

Why: Found last occurrence because next element is different

Step 4: Calculate count as last occurrence index - first occurrence index + 1

count = 3 - 1 + 1 = 3

Why: Number of times 2 appears is the range length

Result:

1 -> [2] -> 2 -> [2] -> 3 -> 4 -> 5
Count of 2 is 3

Annotated Code

DSA C++

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

int findFirstOccurrence(const vector<int>& arr, int target) {
    int left = 0, right = (int)arr.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid; // record current match
            right = mid - 1; // move left to find earlier occurrence
        } else if (arr[mid] < target) {
            left = mid + 1; // target is on right side
        } else {
            right = mid - 1; // target is on left side
        }
    }
    return result;
}

int findLastOccurrence(const vector<int>& arr, int target) {
    int left = 0, right = (int)arr.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid; // record current match
            left = mid + 1; // move right to find later occurrence
        } else if (arr[mid] < target) {
            left = mid + 1; // target is on right side
        } else {
            right = mid - 1; // target is on left side
        }
    }
    return result;
}

int countOccurrences(const vector<int>& arr, int target) {
    int first = findFirstOccurrence(arr, target);
    if (first == -1) return 0; // target not found
    int last = findLastOccurrence(arr, target);
    return last - first + 1;
}

int main() {
    vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
    int target = 2;
    int count = countOccurrences(arr, target);
    cout << "Count of " << target << " is " << count << "\n";
    return 0;
}

result = mid; // record current match right = mid - 1; // move left to find earlier occurrence

record first occurrence candidate and continue searching left side

result = mid; // record current match left = mid + 1; // move right to find later occurrence

record last occurrence candidate and continue searching right side

if (first == -1) return 0; // target not found

handle case when target does not exist in array

return last - first + 1;

calculate total count from first and last occurrence indices

Output

Count of 2 is 3

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach scans entire array O(n), this method is faster by using sorted property

Edge Cases

target not in array

returns 0 because first occurrence search returns -1

DSA C++

if (first == -1) return 0; // target not found

array is empty

returns 0 immediately as no elements to search

DSA C++

while (left <= right) { ... } handles empty by no iterations

all elements are the target

returns array size as count

DSA C++

return last - first + 1;

When to Use This Pattern

When you need to count how many times a number appears in a sorted array, use binary search to find first and last positions to count efficiently.

Common Mistakes

Mistake: Stopping binary search when first match is found instead of continuing to find first occurrence
Fix: Continue searching left side after finding a match to find earliest index

Mistake: Calculating count as last - first without adding 1
Fix: Add 1 to include both first and last indices in count

Summary

Counts how many times a target appears in a sorted array by finding first and last positions.

Use when you want an efficient count of duplicates in a sorted list.

The key is to use binary search twice to find boundaries instead of scanning all elements.