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 list. Since the array is sorted, all the same elements are grouped together. This makes it easier and faster to count them without checking every item. We use special methods to find the first and last place the element appears and then calculate the count.

Why it matters

Without this method, counting occurrences would require checking every item, which is slow for big lists. Using the sorted property lets us find the count quickly, saving time and computer power. This is important in searching, data analysis, and many programs where speed matters. Without it, programs would be slower and less efficient.

Where it fits

Before learning this, you should understand arrays and basic searching methods like linear search. After this, you can learn about binary search and other efficient searching and counting techniques. This topic builds a bridge between simple searching and more advanced data handling.

Mental Model

Core Idea

Find the first and last positions of the element in the sorted array, then subtract to get the total count.

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.

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 are grouped.

A sorted array is a list where elements are arranged in order, like numbers from smallest to largest. Because of this order, if an element appears multiple times, all its copies are next to each other. For example, in [1, 2, 2, 3], the two '2's are side by side.

Result

You know that all copies of the same element are together in the array.

Understanding that duplicates are grouped helps us use faster methods to find counts without checking every element.

2

Foundation

Basic Counting by Checking Each Element

Concept: Count occurrences by scanning the whole array.

To count how many times an element appears, you can look at each item one by one and add 1 if it matches. For example, to count '2' in [1, 2, 2, 3], check each element: 1 (no), 2 (yes), 2 (yes), 3 (no). Total count is 2.

Result

Count is 2 for element '2'.

This method works but is slow for big arrays because it checks every item.

3

Intermediate

Using Binary Search to Find First Occurrence

🤔Before reading on: do you think binary search can find the first occurrence of an element directly or just any occurrence? Commit to your answer.

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

Binary search splits the array in half repeatedly to find an element quickly. To find the first occurrence, when you find the element, keep searching to the left side to see if it appears earlier. Stop when you can't find it earlier.

Result

First occurrence index of '2' in [1, 2, 2, 2, 3] is 1.

Knowing how to adjust binary search to find the first occurrence lets you pinpoint where duplicates start efficiently.

4

Intermediate

Using Binary Search to Find Last Occurrence

🤔Before reading on: do you think finding the last occurrence is similar to finding the first? Commit to your answer.

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

Similar to finding the first occurrence, but when you find the element, keep searching to the right side to find if it appears later. Stop when no later occurrence is found.

Result

Last occurrence index of '2' in [1, 2, 2, 2, 3] is 3.

This method complements the first occurrence search and together they define the full range of duplicates.

5

Intermediate

Calculating Total Count from Indices

Concept: Use the first and last occurrence indices to find the count.

Once you have the first and last positions, subtract the first from the last and add 1. For example, first = 1, last = 3, count = 3 - 1 + 1 = 3.

Result

Count of element '2' is 3.

This simple calculation avoids scanning the array and uses the sorted property for speed.

6

Advanced

Complete C# Implementation with Binary Search

🤔Before reading on: do you think a single binary search can find the count directly? Commit to your answer.

Concept: Combine first and last occurrence searches into a full method to count occurrences.

public static int CountOccurrences(int[] arr, int x) { int first = FindFirst(arr, x); if (first == -1) return 0; int last = FindLast(arr, x); return last - first + 1; } public static int FindFirst(int[] arr, int x) { int low = 0, high = arr.Length - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == x) { result = mid; high = mid - 1; } else if (arr[mid] < x) { low = mid + 1; } else { high = mid - 1; } } return result; } public static int FindLast(int[] arr, int x) { int low = 0, high = arr.Length - 1, result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == x) { result = mid; low = mid + 1; } else if (arr[mid] < x) { low = mid + 1; } else { high = mid - 1; } } return result; } // Example usage: // int[] arr = {1, 2, 2, 2, 3, 4, 5}; // int count = CountOccurrences(arr, 2); // Console.WriteLine(count); // Output: 3

Result

Output: 3

Seeing the full code shows how the two searches work together to count efficiently without scanning the whole array.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think this method works correctly if the element is not in the array? Commit to your answer.

Concept: Understand how the method behaves when the element is missing or at array edges.

If the element is not found, FindFirst returns -1 and CountOccurrences returns 0. If the element is at the start or end, the binary searches still find correct indices. This method runs in O(log n) time, much faster than scanning. It also works with duplicates and single occurrences.

Result

Correct counts for all cases, including zero when element is missing.

Knowing how edge cases are handled prevents bugs and ensures reliable use in real programs.

Under the Hood

The method uses binary search, which repeatedly divides the array in half to find elements quickly. To find the first occurrence, it moves left after finding the element to check for earlier copies. To find the last occurrence, it moves right similarly. This uses the sorted order to avoid checking every element, reducing time from linear to logarithmic.

Why designed this way?

Binary search was designed to speed up searching in sorted data. Counting occurrences by finding boundaries is a natural extension. Alternatives like scanning every element are simpler but slower. This method balances speed and simplicity, making it ideal for large sorted arrays.

Array indices: 0  1  2  3  4  5  6
Array values:  1  2  2  2  3  4  5

FindFirst:
  Start low=0, high=6
  mid=3 (value=2) -> move left high=2
  mid=1 (value=2) -> move left high=0
  mid=0 (value=1) -> move right low=1
  Result=1

FindLast:
  Start low=0, high=6
  mid=3 (value=2) -> move right low=4
  mid=5 (value=4) -> move left high=4
  mid=4 (value=3) -> move left high=3
  Result=3

Myth Busters - 4 Common Misconceptions

Quick: Does binary search always find the first occurrence of an 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. You must modify it to find the first occurrence.

Why it matters: Using unmodified binary search can give wrong counts if you assume the found index is the first occurrence.

Quick: If the element is not in the array, does the count method return -1? Commit yes or no.

Common Belief: If the element is missing, the method returns -1 or an error.

Reality: The method returns 0, meaning no occurrences found, which is the correct count.

Why it matters: Misunderstanding this can cause bugs or crashes when searching for missing elements.

Quick: Is scanning the whole array faster than binary search for counting occurrences? Commit yes or no.

Common Belief: Checking every element is faster or just as fast as binary search for counting.

Reality: Binary search is much faster (O(log n)) than scanning (O(n)) for large sorted arrays.

Why it matters: Using scanning wastes time and resources on big data, slowing down programs.

Quick: Can this method be used on unsorted arrays? Commit yes or no.

Common Belief: This counting method works on any array, sorted or not.

Reality: It only works correctly on sorted arrays because it relies on grouping of duplicates.

Why it matters: Applying it to unsorted arrays gives wrong counts or errors.

Expert Zone

1

The binary search modifications for first and last occurrences are subtle but critical; missing the direction change leads to incorrect indices.

2

When the array contains many duplicates, this method is especially efficient compared to scanning, but for small arrays, scanning might be simpler and fast enough.

3

Edge cases like empty arrays or arrays with one element require careful handling to avoid index errors.

When NOT to use

Do not use this method on unsorted arrays; instead, use a hash map or dictionary to count occurrences. For very small arrays, a simple scan might be more straightforward. If the array changes frequently, maintaining a sorted structure or using balanced trees might be better.

Production Patterns

In real systems, this method is used in search engines, databases, and analytics tools to quickly count items matching a query. It is often combined with other binary search variants for range queries and frequency analysis.

Connections

Binary Search

Builds-on

Understanding how to modify binary search to find boundaries deepens your grasp of searching algorithms and their flexibility.

Hash Maps

Alternative approach

Knowing when to use binary search counting versus hash maps helps choose the best tool for counting in sorted versus unsorted data.

Statistics - Frequency Distribution

Conceptual similarity

Counting occurrences in arrays is like finding frequency of values in data sets, a fundamental idea in statistics and data analysis.

Common Pitfalls

#1 Assuming binary search returns the first occurrence directly.

Wrong approach:

int index = Array.BinarySearch(arr, x);
// Use index as first occurrence without checking left side

Correct approach:

Use modified binary search to find first occurrence by moving left after finding element.

Root cause:

Misunderstanding that standard binary search only guarantees finding an occurrence, not the first.

#2 Counting occurrences by scanning entire array even when sorted.

Wrong approach:

int count = 0;
foreach (int num in arr) {
if (num == x) count++;
}
return count;

Correct approach:

Use binary search to find first and last occurrence and calculate count from indices.

Root cause:

Not leveraging the sorted property leads to inefficient solutions.

#3 Applying this method on unsorted arrays.

Wrong approach:

int count = CountOccurrences(unsortedArr, x); // Using binary search method

Correct approach:

Use a dictionary to count occurrences in unsorted arrays.

Root cause:

Ignoring the requirement that array must be sorted for binary search to work.

Key Takeaways

Counting occurrences in a sorted array is efficient because duplicates are grouped together.

Modified binary search can find the first and last positions of an element quickly, enabling fast counting.

This method runs in logarithmic time, much faster than scanning every element for large arrays.

Handling edge cases like missing elements or array boundaries is essential for correct results.

Understanding when and how to use this method versus alternatives like hash maps is key for practical programming.

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 works only for unsorted arrays.

B. It uses less memory than a linear scan.

C. It reduces the time complexity to O(log n) compared to a linear scan.

D. It counts occurrences without checking the array elements.

Solution

1. Step 1: Understand binary search efficiency

   Binary search divides the search space in half each time, making it faster than checking every element.

2. Step 2: Compare with linear scan

   Linear scan checks each element, taking O(n) time, while binary search takes O(log n) time.

3. Final Answer:

   It reduces the time complexity to O(log n) compared to a linear scan. -> Option C

4. Quick Check:

   Binary search = O(log n) speed [OK]

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

Common Mistakes:

• Thinking binary search works on unsorted arrays
• Confusing time complexity with memory usage
• Assuming binary search counts without element checks

2. Which of the following C# method signatures correctly represents a function to count occurrences of an integer in a sorted array?

easy

A. bool CountOccurrences(int[] arr, int target)

B. int CountOccurrences(int[] arr, int target)

C. int CountOccurrences(int target, int[] arr)

D. void CountOccurrences(int[] arr, int target)

Solution

1. Step 1: Identify return type for count

   The function should return an integer representing the count, so return type must be int.

2. Step 2: Check parameter order and types

   Common convention is array first, then target element; parameters types must match int array and int target.

3. Final Answer:

   int CountOccurrences(int[] arr, int target) -> Option B

4. Quick Check:

   Return count as int, array then target [OK]

Hint: Count returns int; array parameter comes before target [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping parameter order incorrectly
• Returning bool instead of count

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

int[] arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
int count = CountOccurrences(arr, target);
Console.WriteLine(count);

int CountOccurrences(int[] nums, int x) {
    int first = Array.BinarySearch(nums, x);
    if (first < 0) return 0;
    int count = 1;
    int left = first - 1;
    while (left >= 0 && nums[left] == x) {
        count++;
        left--;
    }
    int right = first + 1;
    while (right < nums.Length && nums[right] == x) {
        count++;
        right++;
    }
    return count;
}

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Find first occurrence index using BinarySearch

   BinarySearch finds one occurrence of 2 at index 2.

2. Step 2: Count occurrences left and right of index 2

   Left side: index 1 and 0 checked; index 1 is 2 (count=2), index 0 is 1 (stop). Right side: index 3 is 2 (count=3), index 4 is 3 (stop).

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Occurrences of 2 = 3 [OK]

Hint: BinarySearch finds one index; count neighbors equal to target [OK]

Common Mistakes:

• Assuming BinarySearch returns first occurrence always
• Counting only one side neighbors
• Returning 0 if not found without checking neighbors

4. Identify the bug in the following C# method that counts occurrences of a target in a sorted array:

int CountOccurrences(int[] nums, int target) {
    int first = Array.BinarySearch(nums, target);
    if (first < 0) return 0;
    int count = 1;
    int left = first - 1;
    while (left > 0 && nums[left] == target) {
        count++;
        left--;
    }
    int right = first + 1;
    while (right < nums.Length && nums[right] == target) {
        count++;
        right++;
    }
    return count;
}

medium

A. The method should return -1 if target not found instead of 0.

B. The right boundary check should be 'right <= nums.Length' instead of 'right < nums.Length'.

C. The count variable should start at 0, not 1.

D. The left boundary check should be 'left >= 0' instead of 'left > 0'.

Solution

1. Step 1: Analyze left boundary condition in while loop

   The loop checks 'left > 0', so it skips index 0, missing a possible occurrence at start.

2. Step 2: Correct boundary condition to include index 0

   Changing condition to 'left >= 0' ensures index 0 is checked for target equality.

3. Final Answer:

   The left boundary check should be 'left >= 0' instead of 'left > 0'. -> Option D

4. Quick Check:

   Check array start index 0 with '>= 0' [OK]

Hint: Use '>= 0' to include first array index in left scan [OK]

Common Mistakes:

• Using 'left > 0' misses first element
• Returning -1 instead of 0 when not found
• Starting count at 0 instead of 1
• Using wrong right boundary condition

5. Given a sorted array with possible duplicates, how can you efficiently count occurrences of a target element using two binary searches in C#?

hard

A. Find the first and last occurrence indices of the target using binary search, then calculate count as last - first + 1.

B. Use a single binary search to find any occurrence, then count neighbors linearly.

C. Sort the array again and count occurrences with a linear scan.

D. Use a hash map to store counts of all elements, then retrieve target count.

Solution

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

   Modify binary search to find the lowest index where target appears.

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

   Modify binary search to find the highest index where target appears.

3. Step 3: Calculate count from indices

   Count = last occurrence index - first occurrence index + 1.

4. Final Answer:

   Find the first and last occurrence indices of the target using binary search, then calculate count as last - first + 1. -> Option A

5. Quick Check:

   Count = last - first + 1 using two binary searches [OK]

Hint: Two binary searches find boundaries; subtract indices for count [OK]

Common Mistakes:

• Using linear scan after one binary search
• Sorting array again unnecessarily
• Using hash map instead of binary search