Count Occurrences of Element in Sorted Array in DSA Go - Time & Space Complexity

Time Complexity: Count Occurrences of Element in Sorted Array

O(log n)

Understanding Time Complexity

We want to know how fast we can count how many times a number appears in a sorted list.

How does the time needed change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func countOccurrences(arr []int, target int) int {
    left := binarySearch(arr, target, true)
    if left == -1 {
        return 0
    }
    right := binarySearch(arr, target, false)
    return right - left + 1
}

func binarySearch(arr []int, target int, findFirst bool) int {
    low, high := 0, len(arr)-1
    result := -1
    for low <= high {
        mid := low + (high-low)/2
        if arr[mid] == target {
            result = mid
            if findFirst {
                high = mid - 1
            } else {
                low = mid + 1
            }
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return result
}
    

This code finds the first and last position of the target using binary search, then counts how many times it appears.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The binary search loop inside binarySearch runs repeatedly.
• How many times: Each binary search runs about log₂(n) times, where n is the array size.
• We do two binary searches: one to find the first occurrence, one for the last.

How Execution Grows With Input

As the list gets bigger, the number of steps grows slowly, not directly with the size.

Input Size (n)	Approx. Operations
10	About 2 x 4 = 8 steps
100	About 2 x 7 = 14 steps
1000	About 2 x 10 = 20 steps

Pattern observation: Doubling the input size adds only a few more steps because binary search cuts the search space in half each time.

Final Time Complexity

Time Complexity: O(log n)

This means the time to count occurrences grows slowly as the list grows, making it very efficient.

Common Mistake

[X] Wrong: "Counting occurrences requires checking every element, so it must be O(n)."

[OK] Correct: Because the array is sorted, we can use binary search to jump directly to the target's positions without checking all elements.

Interview Connect

Understanding how to use binary search to count occurrences shows you can use smart searching techniques, a skill valued in many coding challenges.

Self-Check

"What if the array was not sorted? How would the time complexity change?"