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.

Practice

1. What is the main advantage of using binary search to count occurrences of an element in a sorted array?

easy

A. It reduces the search time from linear to logarithmic

B. It sorts the array automatically

C. It uses less memory than linear search

D. It works only for unsorted arrays

Solution

1. Step 1: Understand linear vs binary search time

   Linear search checks each element one by one, taking O(n) time. Binary search divides the search space in half each time, taking O(log n) time.

2. Step 2: Apply binary search to counting occurrences

   Using binary search to find the first and last occurrence of the element reduces the total search time significantly compared to scanning the whole array.

3. Final Answer:

   It reduces the search time from linear to logarithmic -> Option A

4. Quick Check:

   Binary search = faster search [OK]

Hint: Binary search halves search space, speeding up counting [OK]

Common Mistakes:

• Thinking binary search sorts the array
• Confusing memory usage with speed
• Assuming binary search works on unsorted arrays

2. Which of the following C++ function signatures is correct for finding the first occurrence of an element in a sorted array using binary search?

easy

A. int firstOccurrence(int arr[], int x)

B. void firstOccurrence(int arr[], int n, int x)

C. int firstOccurrence(int arr, int n, int x)

D. int firstOccurrence(int arr[], int n, int x)

Solution

1. Step 1: Check parameter types and count

   The function needs the array (int arr[]), its size (int n), and the target element (int x).

2. Step 2: Check return type

   It should return an int index of the first occurrence, so return type is int.

3. Final Answer:

   int firstOccurrence(int arr[], int n, int x) -> Option D

4. Quick Check:

   Correct parameters and return type [OK]

Hint: Function returns index, needs array, size, and target [OK]

Common Mistakes:

• Missing array size parameter
• Wrong return type (void instead of int)
• Incorrect array parameter type

3. What will be the output of the following code snippet?

int arr[] = {1, 2, 2, 2, 3, 4, 5};
int n = 7;
int x = 2;

int countOccurrences(int arr[], int n, int x) {
    int first = -1, last = -1;
    int low = 0, high = n - 1;
    // Find first occurrence
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            first = mid;
            high = mid - 1;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    if (first == -1) return 0;
    low = first; high = n - 1;
    // Find last occurrence
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            last = mid;
            low = mid + 1;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return last - first + 1;
}

std::cout << countOccurrences(arr, n, x) << std::endl;

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Find first occurrence of 2

   Binary search finds first 2 at index 1.

2. Step 2: Find last occurrence of 2

   Binary search finds last 2 at index 3.

3. Step 3: Calculate count

   Count = last - first + 1 = 3 - 1 + 1 = 3.

4. Final Answer:

   3 -> Option A

5. Quick Check:

   Occurrences of 2 = 3 [OK]

Hint: Count = last index - first index + 1 [OK]

Common Mistakes:

• Returning last index instead of count
• Not updating low and high correctly
• Returning 0 when element exists

4. Identify the bug in the following code for counting occurrences of an element in a sorted array:

int countOccurrences(int arr[], int n, int x) {
    int first = -1, last = -1;
    int low = 0, high = n - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            first = mid;
            high = mid - 1;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    if (first == -1) return 0;
    low = first; high = n - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            last = mid;
            low = mid + 1;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return last - first + 1;
}

medium

A. Returning last - first instead of last - first + 1

B. Using 'while (low < high)' instead of 'while (low <= high)' causes missing last element

C. Incorrect calculation of mid index

D. Not initializing 'first' and 'last' to zero

Solution

1. Step 1: Analyze loop condition

   The loops use 'while (low < high)', which misses checking when low equals high, possibly skipping the last element.

2. Step 2: Correct loop condition

   Changing to 'while (low <= high)' ensures all elements are checked, including the last one.

3. Final Answer:

   Using 'while (low < high)' instead of 'while (low <= high)' causes missing last element -> Option B

4. Quick Check:

   Loop condition must include equality [OK]

Hint: Use <= in binary search loops to include all elements [OK]

Common Mistakes:

• Using < instead of <= in loops
• Not updating first and last correctly
• Miscomputing mid index

5. Given a sorted array with possible duplicates, how would you modify the binary search approach to count occurrences of multiple different elements efficiently without repeating the search for each element separately?

hard

A. Sort the array again before each search

B. Run binary search separately for each element to find counts

C. Precompute a frequency map using a single pass, then query counts in O(1)

D. Use linear search for each element to count occurrences

Solution

1. Step 1: Understand repeated binary search cost

   Running binary search for each element separately costs O(m log n) for m queries, which can be expensive.

2. Step 2: Use frequency map for efficiency

   A single pass over the sorted array can build a frequency map (element to count) in O(n). Then queries are O(1) each.

3. Final Answer:

   Precompute a frequency map using a single pass, then query counts in O(1) -> Option C

4. Quick Check:

   Frequency map = fast multiple queries [OK]

Hint: Build frequency map once, then answer queries instantly [OK]

Common Mistakes:

• Running binary search repeatedly for each query
• Sorting array multiple times unnecessarily
• Using linear search for each query