Count Occurrences of Element in Sorted Array in DSA C - Deep Dive

Overview - Count Occurrences of Element in Sorted Array

What is it?

Counting occurrences of an element in a sorted array means finding how many times that element appears in the array. Since the array is sorted, all occurrences of the element are grouped together. This makes it easier and faster to count them than in an unsorted array. The goal is to find the count efficiently without checking every element one by one.

Why it matters

Without this method, counting occurrences would require checking every element, which is slow for large arrays. Efficient counting helps in searching, statistics, and data analysis where quick answers are needed. For example, in a list of sorted names, quickly knowing how many times a name appears can speed up decisions or reports. Without this, programs would be slower and less responsive.

Where it fits

Before learning this, you should understand arrays and basic searching methods like linear and binary search. After this, you can learn more advanced searching and counting techniques, like counting in unsorted arrays or using hash maps. This topic is a stepping stone to mastering efficient data querying in sorted data.

Mental Model

Core Idea

In a sorted array, all copies of the same element are next to each other, so finding the first and last position of that element lets you count its occurrences quickly.

Think of it like...

Imagine a row of identical books on a shelf sorted by title. To count how many copies of one title you have, you find the first copy and the last copy on the shelf, then count all books between them without checking every single book.

Sorted Array: [1, 2, 2, 2, 3, 4, 5]
Element to count: 2
Find first occurrence index: 1
Find last occurrence index: 3
Count = last - first + 1 = 3 - 1 + 1 = 3

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why elements of the same value appear together.

A sorted array is a list of elements arranged in increasing or decreasing order. For example, [1, 2, 2, 3, 4] is sorted in increasing order. Because it is sorted, all identical elements are next to each other. This grouping helps us find and count elements faster than in an unsorted list.

Result

You know that identical elements form a continuous block in the array.

Understanding that identical elements are grouped lets us use special search methods to find their positions quickly.

2

Foundation

Linear Counting Method

Concept: Count occurrences by checking each element one by one.

Start from the beginning of the array and check each element. Increase a counter when the element matches the target. Stop when you reach the end. This method works but can be slow for large arrays.

Result

For array [1, 2, 2, 2, 3], counting 2 gives 3.

Linear counting is simple but inefficient for large sorted arrays because it checks every element.

3

Intermediate

Binary Search Basics

Concept: Use binary search to find an element quickly in a sorted array.

Binary search splits the array in half repeatedly to find the target element. It compares the middle element to the target and decides which half to search next. This reduces the search time from checking all elements to just a few steps.

Result

Finding element 2 in [1, 2, 2, 2, 3] takes fewer steps than linear search.

Binary search is a powerful tool that speeds up finding elements in sorted arrays.

4

Intermediate

Finding First Occurrence with Binary Search

🤔Before reading on: do you think a normal binary search always finds the first occurrence of a repeated element? Commit to yes or no.

Concept: Modify binary search to find the first position where the element appears.

Instead of stopping when you find the element, continue searching the left half to see if the element appears earlier. Keep track of the current found position and update it if you find an earlier one. Stop when no earlier occurrence exists.

Result

For [1, 2, 2, 2, 3], first occurrence of 2 is at index 1.

Knowing how to find the first occurrence helps us locate the start of the element block efficiently.

5

Intermediate

Finding Last Occurrence with Binary Search

🤔Before reading on: do you think finding the last occurrence is the same as finding the first? Commit to yes or no.

Concept: Modify binary search to find the last position where the element appears.

Similar to finding the first occurrence, but now search the right half after finding the element. Update the last found position if you find a later occurrence. Stop when no later occurrence exists.

Result

For [1, 2, 2, 2, 3], last occurrence of 2 is at index 3.

Finding the last occurrence completes the range of the element's positions.

6

Advanced

Counting Occurrences Using First and Last Indices

🤔Before reading on: do you think counting occurrences requires scanning the whole array or just using first and last positions? Commit to your answer.

Concept: Calculate count by subtracting first occurrence index from last occurrence index and adding one.

Once you have the first and last positions, the count is last - first + 1. This avoids scanning the array and runs in O(log n) time due to binary searches.

Result

Count of 2 in [1, 2, 2, 2, 3] is 3 (3 - 1 + 1).

Using first and last indices leverages the sorted property for fast counting.

7

Expert

Handling Elements Not Present in Array

🤔Before reading on: if the element is not in the array, do you think the binary search returns -1 or some other value? Commit to your answer.

Concept: Detect when the element does not exist and return zero count safely.

If the binary search for first or last occurrence returns -1 (not found), then the element is not present. The count is zero. This prevents incorrect counts and errors.

Result

Counting 6 in [1, 2, 2, 2, 3] returns 0.

Handling absence correctly avoids bugs and ensures reliable results.

Under the Hood

Binary search works by repeatedly dividing the search interval in half. For first occurrence, after finding the element, it continues searching left to find earlier copies. For last occurrence, it searches right after finding the element. This uses the sorted order to jump quickly to the target range. The count is computed by subtracting indices, avoiding scanning all elements.

Why designed this way?

This method was designed to improve efficiency over linear search. Sorting groups identical elements, enabling binary search to find boundaries quickly. Alternatives like linear search are simpler but slower. This approach balances speed and simplicity, making it ideal for large sorted datasets.

Array: [1, 2, 2, 2, 3, 4, 5]
Search for 2:
 ┌─────────────┐
 │ Entire array│
 └─────┬───────┘
       ↓
 ┌─────────────┐
 │ Middle element│
 └─────┬───────┘
       ↓
If middle == 2, search left half for first occurrence
If middle == 2, search right half for last occurrence
Result: first index = 1, last index = 3
Count = 3 - 1 + 1 = 3

Myth Busters - 3 Common Misconceptions

Quick: Does a normal binary search always find the first occurrence of a repeated element? Commit yes or no.

Common Belief: Binary search always returns the first occurrence of the element.

Reality: Standard binary search returns any occurrence, not necessarily the first.

Why it matters: Assuming it returns the first can cause wrong counts and bugs in programs.

Quick: If the element is not in the array, does binary search return -1 or an index? Commit your answer.

Common Belief: Binary search always returns a valid index, even if the element is missing.

Reality: Binary search returns -1 or a special value indicating not found when the element is absent.

Why it matters: Ignoring this leads to incorrect counts or accessing invalid array positions.

Quick: Is linear search faster than binary search for large sorted arrays? Commit yes or no.

Common Belief: Linear search is just as fast as binary search for sorted arrays.

Reality: Binary search is much faster (logarithmic time) than linear search (linear time) for large arrays.

Why it matters: Using linear search on large data causes slow programs and poor user experience.

Expert Zone

1

Binary search for first and last occurrence must carefully handle mid calculation to avoid infinite loops.

2

Edge cases like all elements being the target or none being the target require special attention.

3

Using built-in language functions for lower_bound and upper_bound can simplify implementation and improve reliability.

When NOT to use

This method only works efficiently if the array is sorted. For unsorted arrays, use hash maps or linear counting. If data changes frequently, maintaining sorted order may be costly, so other data structures like balanced trees or hash tables are better.

Production Patterns

In real systems, counting occurrences in sorted logs or event streams uses this method for fast analytics. Database indexes rely on similar binary search techniques to count rows matching a key. Search engines use these patterns to quickly count documents containing a word.

Connections

Binary Search

Builds-on

Understanding counting occurrences deeply depends on mastering binary search variations.

Hash Maps

Alternative approach

Hash maps count occurrences efficiently in unsorted data, showing different tradeoffs compared to sorted arrays.

Library Book Cataloging

Similar pattern

Counting copies of a book in a sorted catalog uses the same logic of finding first and last positions to count quickly.

Common Pitfalls

#1 Using normal binary search result as count without checking first and last positions.

Wrong approach:

int count = 1; // assuming one occurrence if found
int index = binary_search(arr, n, x);
if (index == -1) count = 0;

Correct approach:

int first = find_first_occurrence(arr, n, x);
int last = find_last_occurrence(arr, n, x);
int count = (first == -1) ? 0 : (last - first + 1);

Root cause:

Misunderstanding that binary search returns any occurrence, not the full range.

#2 Not handling the case when element is not found, leading to negative indices or wrong counts.

Wrong approach:

int first = find_first_occurrence(arr, n, x);
int last = find_last_occurrence(arr, n, x);
int count = last - first + 1; // no check for -1

Correct approach:

int first = find_first_occurrence(arr, n, x);
if (first == -1) return 0;
int last = find_last_occurrence(arr, n, x);
int count = last - first + 1;

Root cause:

Ignoring the possibility that the element is missing.

#3 Using linear search on large sorted arrays causing slow performance.

Wrong approach:

int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == x) count++;
}

Correct approach:

Use binary search based first and last occurrence methods for O(log n) performance.

Root cause:

Not leveraging the sorted property of the array.

Key Takeaways

In a sorted array, identical elements appear together, allowing efficient counting by finding their first and last positions.

Binary search can be adapted to find the first and last occurrence of an element, not just any occurrence.

Counting occurrences by subtracting indices is much faster than scanning the entire array.

Always handle the case when the element is not present to avoid errors.

This method is a classic example of using data structure properties to optimize algorithms.

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