Count Occurrences of Element in Sorted Array in DSA C

Mental Model

In a sorted list, all copies of the same 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. To count how many copies of one book are there, find the first copy and the last copy, then count all books in between.

Sorted array: [1, 2, 2, 2, 3, 4, 5]
Find element 2:
Index:       0  1  2  3  4  5  6
Values:     1-> 2-> 2-> 2-> 3-> 4-> 5
               ↑           ↑
           first 2      last 2

Dry Run Walkthrough

Input: array: [1, 2, 2, 2, 3, 4, 5], element to count: 2

Goal: Find how many times 2 appears in the sorted array

Step 1: Find first occurrence of 2 using binary search

Array: [1, 2, 2, 2, 3, 4, 5]
Search range: indices 0 to 6
Mid index 3 value 2 matches target, move left to find first occurrence

Why: We want the earliest index where 2 appears

Step 2: Continue searching left half from indices 0 to 2

Search range: indices 0 to 2
Mid index 1 value 2 matches target, move left again

Why: Check if there is an earlier 2

Step 3: Search left half from indices 0 to 0

Search range: indices 0 to 0
Mid index 0 value 1 less than target, move right

Why: No earlier 2 found, first occurrence is at index 1

Step 4: Find last occurrence of 2 using binary search

Search range: indices 0 to 6
Mid index 3 value 2 matches target, move right to find last occurrence

Why: We want the latest index where 2 appears

Step 5: Continue searching right half from indices 4 to 6

Search range: indices 4 to 6
Mid index 5 value 4 greater than target, move left

Why: Check if last occurrence is before index 5

Step 6: Search right half from indices 4 to 4

Search range: indices 4 to 4
Mid index 4 value 3 greater than target, move left

Why: No later 2 found, last occurrence is at index 3

Step 7: Calculate count as last index - first index + 1 = 3 - 1 + 1 = 3

Count of 2 is 3

Why: Number of occurrences is the range length between first and last

Result:

Final count: 3

Annotated Code

DSA C

#include <stdio.h>

int findFirst(int arr[], int n, int x) {
    int low = 0, high = n - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            result = mid; // record current match
            high = mid - 1; // move left to find earlier occurrence
        } else if (arr[mid] < x) {
            low = mid + 1; // move right
        } else {
            high = mid - 1; // move left
        }
    }
    return result;
}

int findLast(int arr[], int n, int x) {
    int low = 0, high = n - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            result = mid; // record current match
            low = mid + 1; // move right to find later occurrence
        } else if (arr[mid] < x) {
            low = mid + 1; // move right
        } else {
            high = mid - 1; // move left
        }
    }
    return result;
}

int countOccurrences(int arr[], int n, int x) {
    int first = findFirst(arr, n, x);
    if (first == -1) return 0; // element not found
    int last = findLast(arr, n, x);
    return last - first + 1;
}

int main() {
    int arr[] = {1, 2, 2, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    int count = countOccurrences(arr, n, x);
    printf("Count of %d is %d\n", x, count);
    return 0;
}

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

record first occurrence candidate and continue searching left

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

record last occurrence candidate and continue searching right

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

handle case when element does not exist in array

return last - first + 1;

calculate total count from first and last 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, no extra data structures

vs Alternative: Naive approach scans entire array O(n), this method is faster for large sorted arrays

Edge Cases

Element not present in array

Returns count 0 because first occurrence search returns -1

DSA C

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

Array with single element equal to target

Returns count 1 correctly

DSA C

return last - first + 1;

All elements are the target

Returns count equal to array length

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 list, use binary search to find first and last positions for efficient counting.

Common Mistakes

Mistake: Stopping binary search immediately when target is found without searching for first or last occurrence
Fix: Continue searching left or right after finding target to find exact first or last index

Mistake: Not handling case when element is not found, causing wrong count
Fix: Check if first occurrence is -1 and return 0 if so

Summary

Counts how many times a given element appears in a sorted array.

Use when you want fast counting of duplicates in sorted data.

The key is to find the first and last positions of the element using binary search.

Practice

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

easy

A. It uses less memory than linear search

B. It sorts the array automatically

C. It reduces the search time from linear to logarithmic

D. It works only on unsorted arrays

Solution

1. Step 1: Understand binary search efficiency

   Binary search divides the search space in half each time, reducing time complexity to O(log n).

2. Step 2: Compare with linear search

   Linear search checks each element one by one, taking O(n) time, which is slower for large arrays.

3. Final Answer:

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

4. Quick Check:

   Binary search = faster search [OK]

Hint: Binary search halves search space each step [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 code snippets correctly declares a function to count occurrences of an integer in a sorted array?

easy

A. void countOccurrences(int arr[], int n, int x);

B. int countOccurrences(int arr[], int n, int x);

C. int countOccurrences(int arr, int n, int x);

D. int countOccurrences(int arr[], int x);

Solution

1. Step 1: Check function return type and parameters

   The function should return an int (count), take array, size, and target element as parameters.

2. Step 2: Validate parameter types

   Array parameter must be int arr[] or int *arr, size as int n, and target as int x.

3. Final Answer:

   int countOccurrences(int arr[], int n, int x); -> Option B

4. Quick Check:

   Correct function signature = int countOccurrences(int arr[], int n, int x); [OK]

Hint: Function returns count as int, array passed as int[] [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Missing array size parameter

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

int arr[] = {1, 2, 2, 2, 3, 4, 5};
int n = 7;
int x = 2;
int count = 0;
for (int i = 0; i < n; i++) {
    if (arr[i] == x) count++;
}
printf("%d", count);

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Iterate through the array and count matches

   Elements equal to 2 are at indices 1, 2, and 3, so count increments 3 times.

2. Step 2: Print the count

   The final count is 3, so printf outputs 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count of 2 in array = 3 [OK]

Hint: Count elements equal to x by scanning array once [OK]

Common Mistakes:

• Counting only first occurrence
• Off-by-one errors in loop
• Printing count before loop ends

4. Identify the error in the following C function intended to count occurrences of x in a sorted array using binary search:

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

medium

A. Incrementing mid inside the loop does not change low or high

B. The loop condition should be low < high

C. count should be initialized to -1

D. The function should return void

Solution

1. Step 1: Analyze loop variables and updates

   Incrementing mid does not affect low or high, so loop may become infinite or incorrect.

2. Step 2: Understand binary search update rules

   To move search window, low or high must be updated, not mid.

3. Final Answer:

   Incrementing mid inside the loop does not change low or high -> Option A

4. Quick Check:

   mid++ does not move search window [OK]

Hint: Update low/high, not mid, to move binary search window [OK]

Common Mistakes:

• Changing mid instead of low/high
• Wrong loop condition causing infinite loop
• Incorrect return type

5. Given a sorted array arr = {1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 5}, write a function that uses binary search to count occurrences of x = 5. What is the count returned?

hard

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Use binary search to find first occurrence of 5

   First 5 is at index 7.

2. Step 2: Use binary search to find last occurrence of 5

   Last 5 is at index 10.

3. Step 3: Calculate count as last - first + 1

   Count = 10 - 7 + 1 = 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   Count of 5 in array = 4 [OK]

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

Common Mistakes:

• Counting total elements instead of occurrences
• Off-by-one errors in count calculation
• Using linear search instead of binary search