Count Occurrences of Element in Sorted Array in DSA Python

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 in between.

Sorted array: [1, 2, 2, 2, 3, 4, 5]
Find element 2:
Start index -> [2, 2, 2] ← End index
Count = end - start + 1

Dry Run Walkthrough

Input: array: [1, 2, 2, 2, 3, 4, 5], element: 2

Goal: Find how many times 2 appears in the sorted array

Step 1: Find first occurrence of 2 using binary search

Array: [1, 2, 2, 2, 3, 4, 5]
First occurrence index found at 1

Why: We need the first place 2 appears to start counting

Step 2: Find last occurrence of 2 using binary search

Array: [1, 2, 2, 2, 3, 4, 5]
Last occurrence index found at 3

Why: We need the last place 2 appears to end counting

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

Count = 3 - 1 + 1 = 3

Why: Counting all elements between first and last occurrence

Result:

Final count: 3

Annotated Code

DSA Python

class SortedArray:
    def __init__(self, arr):
        self.arr = arr

    def find_first(self, x):
        low, high = 0, len(self.arr) - 1
        result = -1
        while low <= high:
            mid = (low + high) // 2
            if self.arr[mid] == x:
                result = mid  # record this index
                high = mid - 1  # search left side for earlier occurrence
            elif self.arr[mid] < x:
                low = mid + 1
            else:
                high = mid - 1
        return result

    def find_last(self, x):
        low, high = 0, len(self.arr) - 1
        result = -1
        while low <= high:
            mid = (low + high) // 2
            if self.arr[mid] == x:
                result = mid  # record this index
                low = mid + 1  # search right side for later occurrence
            elif self.arr[mid] < x:
                low = mid + 1
            else:
                high = mid - 1
        return result

    def count_occurrences(self, x):
        first = self.find_first(x)
        if first == -1:
            return 0  # element not found
        last = self.find_last(x)
        return last - first + 1

# Driver code
arr = [1, 2, 2, 2, 3, 4, 5]
sa = SortedArray(arr)
count = sa.count_occurrences(2)
print(count)

if self.arr[mid] == x:

Check if middle element matches target

result = mid # record this index

Save current match index

high = mid - 1 # search left side for earlier occurrence

Move left to find first occurrence

low = mid + 1 # search right side for later occurrence

Move right to find last occurrence

if first == -1: return 0 # element not found

Return zero if element not found

return last - first + 1

Calculate total count of occurrences

Output

3

Complexity Analysis

Time: O(log n) because we use binary search twice to find first and last positions

Space: O(1) because we only use a few variables, no extra space proportional to input

vs Alternative: Naive approach scans entire array O(n), this method is faster for large sorted arrays

Edge Cases

Element not present in array

Returns 0 because first occurrence search returns -1

DSA Python

if first == -1:
    return 0  # element not found

Array with all elements same as target

Counts entire array length correctly

DSA Python

return last - first + 1

Array with single element equal to target

Returns 1 as count

DSA Python

return last - first + 1

When to Use This Pattern

When you see a sorted array and need to count how many times a number appears, use binary search to find first and last positions for efficient counting.

Common Mistakes

Mistake: Using linear scan to count occurrences in a sorted array
Fix: Use binary search to find first and last occurrence for O(log n) time

Mistake: Not updating search boundaries correctly when finding first or last occurrence
Fix: Adjust low or high pointers properly to continue searching left or right side

Summary

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

Use when you have a sorted list and want to count occurrences quickly.

The key is to find the first and last positions of the element using binary search.

Practice

1. What does the problem "Count Occurrences of Element in Sorted Array" ask you to find?

easy

A. The number of times a given element appears in a sorted array

B. The sum of all elements in the array

C. The largest element in the array

D. The position of the first element in the array

Solution

1. Step 1: Understand the problem statement

   The problem asks to find how many times a specific element appears in a sorted array.

2. Step 2: Identify the required output

   The output is the count of occurrences of that element, not its position or sum.

3. Final Answer:

   The number of times a given element appears in a sorted array -> Option A

4. Quick Check:

   Count occurrences = number of times element appears [OK]

Hint: Count how many times the element repeats in the sorted list [OK]

Common Mistakes:

• Confusing count with element position
• Trying to sum elements instead of counting
• Ignoring that array is sorted

2. Which of the following Python code snippets correctly counts occurrences of x in a sorted list arr using built-in methods?

easy

A. count = arr.find(x)

B. count = arr.count(x)

C. count = arr.index(x)

D. count = arr.length(x)

Solution

1. Step 1: Recall Python list methods

   count() returns how many times an element appears in a list.

2. Step 2: Check other methods

   find() and index() find positions, not counts; length() is invalid.

3. Final Answer:

   count = arr.count(x) -> Option B

4. Quick Check:

   Use count() to get occurrences [OK]

Hint: Use list.count(element) to get occurrences fast [OK]

Common Mistakes:

• Using index() instead of count()
• Trying to use find() which is for strings
• Using length() which is not a list method

3. What is the output of the following code?

def count_occurrences(arr, x):
    return arr.count(x)

arr = [1, 2, 2, 2, 3, 4]
x = 2
print(count_occurrences(arr, x))

medium

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Understand the input array and element

   The array is [1, 2, 2, 2, 3, 4] and the element to count is 2.

2. Step 2: Count occurrences of 2 in the array

   2 appears three times in the array.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count of 2 in array = 3 [OK]

Hint: Count how many times 2 appears in the list [OK]

Common Mistakes:

• Counting unique elements instead of occurrences
• Miscounting the number of 2s
• Confusing count with index

4. Find the error in this code that tries to count occurrences of x in a sorted array arr:

def count_occurrences(arr, x):
    count = 0
    for i in range(len(arr)):
        if arr[i] == x:
            count += 1
        else:
            break
    return count

arr = [1, 2, 2, 2, 3, 4]
x = 2
print(count_occurrences(arr, x))

medium

A. The loop breaks too early, missing some occurrences

B. The count variable is not initialized

C. The function does not return any value

D. The comparison operator is incorrect

Solution

1. Step 1: Analyze the loop and break condition

   The loop breaks on first element not equal to x, so it counts only consecutive occurrences from start.

2. Step 2: Check the input array and x

   Since x=2 and array starts with 1, the loop breaks immediately, count remains 0.

3. Final Answer:

   The loop breaks too early, missing some occurrences -> Option A

4. Quick Check:

   Break stops counting early, so count is wrong [OK]

Hint: Don't break loop; count all matching elements [OK]

Common Mistakes:

• Breaking loop on first non-match in unsorted array
• Not counting all occurrences
• Assuming array starts with x

5. Given a sorted array arr = [1, 2, 2, 2, 3, 4, 4, 5], which approach efficiently counts occurrences of x = 4 without scanning the entire array?

hard

A. Use a for loop to count all 4s by scanning from start to end

B. Use arr.count(4) which scans entire array internally

C. Use binary search to find first and last positions of 4, then calculate count

D. Sort the array again and count 4s

Solution

1. Step 1: Understand the array is sorted

   Since the array is sorted, all 4s are together in a block.

2. Step 2: Use binary search to find first and last occurrence

   Binary search finds first and last index of 4 quickly, then count = last - first + 1.

3. Step 3: Compare other options

   For loop and count() scan entire array, sorting again is unnecessary and inefficient.

4. Final Answer:

   Use binary search to find first and last positions of 4, then calculate count -> Option C

5. Quick Check:

   Binary search + index difference = count [OK]

Hint: Find first and last index with binary search, subtract [OK]

Common Mistakes:

• Scanning entire array instead of using binary search
• Sorting array again unnecessarily
• Using count() without considering efficiency