Count Occurrences of Element in Sorted Array in DSA C# - Execution Trace

Concept Flow - Count Occurrences of Element in Sorted Array

Start

↓

Find first occurrence of target

↓

Find last occurrence of target

↓

Calculate count = last - first + 1

↓

Return count

↓

End

We find where the target first appears, then where it last appears, then count how many times it occurs.

Execution Sample

DSA C#

int CountOccurrences(int[] arr, int target) {
  int first = FindFirst(arr, target);
  if (first == -1) return 0;
  int last = FindLast(arr, target);
  return last - first + 1;
}

This code counts how many times target appears in a sorted array by finding first and last positions.

Execution Table

Step	Operation	Index Checked	Comparison Result	Pointer Changes	Visual State
1	FindFirst: start binary search	-	-	low=0, high=8	[1,2,2,2,3,4,5,5,6]
2	FindFirst: mid=4	4	arr[4]=3 > 2	high=3	[1,2,2,2,3,4,5,5,6]
3	FindFirst: mid=1	1	arr[1]=2 == 2	high=0, first=1	[1,2,2,2,3,4,5,5,6]
4	FindFirst: mid=0	0	arr[0]=1 < 2	low=1	[1,2,2,2,3,4,5,5,6]
5	FindFirst: loop ends	-	-	first=1	[1,2,2,2,3,4,5,5,6]
6	FindLast: start binary search	-	-	low=0, high=8	[1,2,2,2,3,4,5,5,6]
7	FindLast: mid=4	4	arr[4]=3 > 2	high=3	[1,2,2,2,3,4,5,5,6]
8	FindLast: mid=2	2	arr[2]=2 == 2	low=3, last=2	[1,2,2,2,3,4,5,5,6]
9	FindLast: mid=3	3	arr[3]=2 == 2	low=4, last=3	[1,2,2,2,3,4,5,5,6]
10	FindLast: loop ends	-	-	last=3	[1,2,2,2,3,4,5,5,6]
11	Calculate count	-	-	count = 3 - 1 + 1 = 3	[1,2,2,2,3,4,5,5,6]
12	Return count	-	-	return 3	[1,2,2,2,3,4,5,5,6]

💡 Binary searches end when low > high; count calculated as last - first + 1.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 9	After Step 10	Final
low	0	0	1	4	4	4
high	8	0	0	3	3	3
first	-1	1	1	1	1	1
last	-1	-1	-1	3	3	3
count	-	-	-	-	-	3

Key Moments - 3 Insights

Why do we update 'high' when arr[mid] equals target in FindFirst?

Because we want to find the first occurrence, so we continue searching left by moving 'high' to mid-1 (see step 3 in execution_table).

Why do we update 'low' when arr[mid] equals target in FindLast?

Because we want to find the last occurrence, so we continue searching right by moving 'low' to mid+1 (see steps 8 and 9 in execution_table).

What if the target is not found in the array?

FindFirst returns -1, so we return 0 immediately (see step 5 where first is checked).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'first' after step 5?

A 0

B 1

C -1

D 3

💡 Hint

Check the 'Pointer Changes' column at step 5 in execution_table.

At which step does the condition for FindLast become false, ending the loop?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look for the step where 'loop ends' is mentioned in the Operation column.

If the target was 5 instead of 2, how would the 'first' pointer change after FindFirst?

A It would be 6

B It would be 7

C It would be -1

D It would be 8

💡 Hint

Consider where 5 first appears in the array [1,2,2,2,3,4,5,5,6].

Concept Snapshot

Count Occurrences in Sorted Array:
- Use binary search to find first occurrence of target.
- Use binary search to find last occurrence of target.
- Count = last index - first index + 1.
- If target not found, count is 0.
- Efficient O(log n) time due to binary search.

Full Transcript

To count how many times a number appears in a sorted array, we find the first and last places it appears using binary search. We start by searching for the first occurrence: if the middle element is the target, we keep searching left to find if it appears earlier. For the last occurrence, if the middle element is the target, we search right to find if it appears later. Once we have both positions, we subtract first from last and add one to get the count. If the target is not found, we return zero. This method is fast because it uses binary search, which cuts the search space in half each time.

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