Number of Occurrences in Sorted Array in O(log n) Time Using Python

Given a sorted array of integers nums, count the number of occurrences of a given value.

Example:

Input: nums = [1, 2, 2, 2, 4, 5], value = 2
Output: 3
Explanation: the value 2 appears 3 times in the array

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to count the occurrences of a given value in a sorted array efficiently. The significance of this problem lies in its applications in search algorithms and data analysis where quick lookups are essential. A common pitfall is to use a linear search which would result in O(n) time complexity, which is not optimal for large datasets.

Approach

To solve this problem efficiently, we can use binary search to find the first and last occurrences of the given value. The difference between these indices plus one will give us the count of occurrences.

Naive Solution

A naive solution would be to iterate through the array and count the occurrences of the value. This would take O(n) time, which is not efficient for large arrays.

Optimized Solution

We can use binary search to find the first and last occurrences of the value. This approach will take O(log n) time, which is optimal for this problem.

Finding the First Occurrence

We can use a modified binary search to find the first occurrence of the value. If the middle element is greater than or equal to the value, we move to the left half; otherwise, we move to the right half.

Finding the Last Occurrence

Similarly, we can use a modified binary search to find the last occurrence of the value. If the middle element is less than or equal to the value, we move to the right half; otherwise, we move to the left half.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize two functions to find the first and last occurrences of the value using binary search.
In the first occurrence function, if the middle element is greater than or equal to the value, move to the left half; otherwise, move to the right half.
In the last occurrence function, if the middle element is less than or equal to the value, move to the right half; otherwise, move to the left half.
Calculate the number of occurrences by subtracting the first index from the last index and adding one.

Code Implementation

def find_first_occurrence(nums, value):
    left, right = 0, len(nums) - 1
    first_occurrence = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= value:
            if nums[mid] == value:
                first_occurrence = mid
            right = mid - 1
        else:
            left = mid + 1
    return first_occurrence

def find_last_occurrence(nums, value):
    left, right = 0, len(nums) - 1
    last_occurrence = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] <= value:
            if nums[mid] == value:
                last_occurrence = mid
            left = mid + 1
        else:
            right = mid - 1
    return last_occurrence

def count_occurrences(nums, value):
    first_occurrence = find_first_occurrence(nums, value)
    if first_occurrence == -1:
        return 0
    last_occurrence = find_last_occurrence(nums, value)
    return last_occurrence - first_occurrence + 1

# Example usage
nums = [1, 2, 2, 2, 4, 5]
value = 2
print(count_occurrences(nums, value))  # Output: 3

Complexity Analysis

The time complexity of both the first and last occurrence functions is O(log n) because we are using binary search. The space complexity is O(1) as we are not using any extra space.

Edge Cases

Some potential edge cases include:

The value does not exist in the array. The function should return 0.
All elements in the array are the same as the value. The function should return the length of the array.
The array is empty. The function should return 0.

Testing

To test the solution comprehensively, we should include a variety of test cases:

Simple cases with a few elements.
Cases where the value does not exist in the array.
Cases with large arrays to test the efficiency.
Edge cases as mentioned above.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints.
Think about the most efficient way to solve the problem.
Break down the problem into smaller sub-problems.
Consider edge cases and test your solution thoroughly.

Conclusion

In this blog post, we discussed how to count the number of occurrences of a value in a sorted array efficiently using binary search. We provided a detailed explanation of the algorithm, code implementation, and complexity analysis. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice problems, consider the following resources: