Count Occurrences of Element in Sorted Array in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main advantage of counting occurrences in a sorted array compared to an unsorted array?

In a sorted array, all occurrences of an element are grouped together. This allows us to use efficient methods like binary search to find the first and last positions of the element, making counting faster than scanning the entire array.

intermediate

Explain how binary search helps in counting occurrences of an element in a sorted array.

Binary search can find the first occurrence (left boundary) and last occurrence (right boundary) of the element quickly. The count is then the difference between these two positions plus one.

beginner

What is the time complexity of counting occurrences of an element in a sorted array using binary search?

The time complexity is O(log n) because binary search is used twice (once for first occurrence and once for last occurrence), and each binary search runs in O(log n).

intermediate

In C, what should you be careful about when implementing binary search to find boundaries in an array?

Be careful with index calculations to avoid overflow (use mid = low + (high - low) / 2), and ensure the loop conditions correctly move the search boundaries to find first or last occurrence.

beginner

If the element is not present in the sorted array, what should the count of occurrences be?

The count should be zero because the element does not appear in the array.

What is the first step to count occurrences of an element in a sorted array?

A Find the first occurrence of the element using binary search

B Scan the entire array from start to end

C Sort the array first

D Find the maximum element in the array

Finding the first occurrence using binary search is the first step to efficiently count occurrences.

How do you calculate the total count of an element after finding its first and last positions?

A last position * first position

B last position - first position + 1

C first position - last position

D last position + first position

The count is the difference between last and first positions plus one.

What is the time complexity of counting occurrences using binary search in a sorted array of size n?

A O(log n)

B O(n)

C O(n log n)

D O(1)

Binary search runs in O(log n), so counting occurrences using two binary searches is O(log n).

If the element is not found in the array, what should the function return as count?

A 1

B -1

C 0

D Array size

If the element is not present, the count of occurrences is zero.

Which of these is a safe way to calculate mid index in binary search to avoid overflow?

A mid = low * high

B mid = (low + high) / 2

C mid = high - low

D mid = low + (high - low) / 2

Using mid = low + (high - low) / 2 prevents integer overflow.

Describe the steps to count occurrences of an element in a sorted array using binary search.

Think about how to find boundaries of the element in the array.

Explain why binary search is efficient for counting occurrences in a sorted array compared to scanning the whole array.

Compare time complexities and array order.

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