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

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 efficiently count the number of occurrences of a given value in a sorted array. 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, not meeting the problem's requirements.

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 involve iterating through the array and counting the occurrences of the value. This approach has a time complexity of O(n), which is not optimal for large arrays.

Optimized Solution

We can optimize the solution using binary search to find the first and last occurrences of the value. This approach leverages the sorted nature of the array and achieves O(log n) time complexity.

Finding the First Occurrence

We 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 the search to the left half; otherwise, we move to the right half.

Finding the Last Occurrence

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

Algorithm

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

Initialize two binary search functions to find the first and last occurrences of the value.
In the first binary search, adjust the search range based on whether the middle element is greater than or equal to the value.
In the second binary search, adjust the search range based on whether the middle element is less than or equal to the value.
Calculate the number of occurrences by subtracting the first index from the last index and adding one.

Code Implementation


#include <iostream>
#include <vector>

using namespace std;

// Function to find the first occurrence of value
int findFirstOccurrence(const vector<int>& nums, int value) {
    int left = 0, right = nums.size() - 1, ans = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= value) {
            if (nums[mid] == value) ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

// Function to find the last occurrence of value
int findLastOccurrence(const vector<int>& nums, int value) {
    int left = 0, right = nums.size() - 1, ans = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= value) {
            if (nums[mid] == value) ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

// Function to count the number of occurrences of value
int countOccurrences(const vector<int>& nums, int value) {
    int first = findFirstOccurrence(nums, value);
    if (first == -1) return 0; // Value not found
    int last = findLastOccurrence(nums, value);
    return last - first + 1;
}

int main() {
    vector<int> nums = {1, 2, 2, 2, 4, 5};
    int value = 2;
    cout << "Number of occurrences of " << value << ": " << countOccurrences(nums, value) << endl;
    return 0;
}

Complexity Analysis

The time complexity of both binary search functions is O(log n), and since we perform two binary searches, the overall time complexity is O(log n). The space complexity is O(1) as we are not using any extra space apart from a few variables.

Edge Cases

Potential edge cases include:

The value is not present in the array.
All elements in the array are the same as the value.
The array is empty.

Our algorithm handles these cases by returning 0 if the value is not found and correctly calculating the occurrences otherwise.

Testing

To test the solution comprehensively, consider the following test cases:

Array: [1, 2, 2, 2, 4, 5], Value: 2 (Expected output: 3)
Array: [1, 1, 1, 1, 1], Value: 1 (Expected output: 5)
Array: [1, 2, 3, 4, 5], Value: 6 (Expected output: 0)
Array: [], Value: 1 (Expected output: 0)

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Leverage the properties of the data (e.g., sorted array) to optimize the solution.
Break down the problem into smaller subproblems and solve each one efficiently.
Practice similar problems to improve your problem-solving skills and familiarity with algorithms.

Conclusion

In this blog post, we discussed how to count the number of occurrences of a value in a sorted array using an efficient O(log n) algorithm. We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: