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 title there are, find the first copy and the last copy, then count all books between them.

Array: [1, 2, 2, 2, 3, 4, 5]
          ↑           ↑
       first       last
       occurrence  occurrence

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 array

Step 1: Find first occurrence of 2 using binary search

Array: [1, 2, 2, 2, 3, 4, 5]
Index range checked narrows to left side
First occurrence found at index 1

Why: We need to find where 2 starts to count all its copies

Step 2: Find last occurrence of 2 using binary search

Array: [1, 2, 2, 2, 3, 4, 5]
Index range checked narrows to right side
Last occurrence found at index 3

Why: We need to find where 2 ends to count all its copies

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

Count = 3 - 1 + 1 = 3

Why: Counting all elements from first to last occurrence gives total copies

Result:

Array: [1, 2, 2, 2, 3, 4, 5]
Count of 2 = 3

Annotated Code

DSA C#

using System;

class SortedArrayCounter
{
    // Find first occurrence of target using binary search
    static int FindFirst(int[] arr, int target)
    {
        int left = 0, right = arr.Length - 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 right side
            }
            else
            {
                right = mid - 1; // target is left side
            }
        }
        return result;
    }

    // Find last occurrence of target using binary search
    static int FindLast(int[] arr, int target)
    {
        int left = 0, right = arr.Length - 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 right side
            }
            else
            {
                right = mid - 1; // target is left side
            }
        }
        return result;
    }

    // Count occurrences by finding first and last index
    public static int CountOccurrences(int[] arr, int target)
    {
        int first = FindFirst(arr, target);
        if (first == -1) return 0; // target not found
        int last = FindLast(arr, target);
        return last - first + 1;
    }

    static void Main()
    {
        int[] arr = {1, 2, 2, 2, 3, 4, 5};
        int target = 2;
        int count = CountOccurrences(arr, target);
        Console.WriteLine($"Count of {target} = {count}");
    }
}

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

record first occurrence and continue searching left side

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

record last occurrence 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 indices

Output

Count of 2 = 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

target not in array

returns 0 because first occurrence search returns -1

DSA C#

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

array with one element equal to target

returns 1 as first and last occurrence are same index

DSA C#

return last - first + 1;

array with all elements equal to target

returns length of array 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 list, use binary search to find first and last positions to count efficiently.

Common Mistakes

Mistake: Stopping binary search immediately when target is found instead of searching for first or last occurrence
Fix: Continue searching left side for first occurrence and right side for last occurrence after finding a match

Summary

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

Use when you want a fast count of duplicates in a sorted list without scanning all elements.

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 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