Number of Occurrences in Sorted Array (O(log n) Time Complexity, JavaScript)

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 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 not meet the required time complexity of O(log n). ## Approach ### 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 datasets. ### Optimized Solution To achieve the required O(log n) time complexity, we can use binary search to find the first and last occurrences of the value. The difference between these indices plus one will give us the count of the value in the array. ### Steps to Solve 1. **Find the First Occurrence**: Use binary search to find the first index where the value appears. 2. **Find the Last Occurrence**: Use binary search to find the last index where the value appears. 3. **Calculate the Count**: The count is the difference between the last and first indices plus one. ## Algorithm ### Finding the First Occurrence 1. Initialize `left` to 0 and `right` to the length of the array minus one. 2. Perform binary search: - Calculate `mid` as the average of `left` and `right`. - If `nums[mid]` is greater than or equal to the value, move `right` to `mid - 1`. - If `nums[mid]` is less than the value, move `left` to `mid + 1`. - If `nums[mid]` equals the value, update `result` to `mid` and move `right` to `mid - 1` to find the first occurrence. ### Finding the Last Occurrence 1. Initialize `left` to 0 and `right` to the length of the array minus one. 2. Perform binary search: - Calculate `mid` as the average of `left` and `right`. - If `nums[mid]` is greater than the value, move `right` to `mid - 1`. - If `nums[mid]` is less than or equal to the value, update `result` to `mid` and move `left` to `mid + 1` to find the last occurrence. ### Code Implementation

/**
 * Function to find the first occurrence of a value in a sorted array
 * @param {number[]} nums - Sorted array of integers
 * @param {number} value - Value to find
 * @return {number} - Index of the first occurrence
 */
function findFirstOccurrence(nums, value) {
    let left = 0;
    let right = nums.length - 1;
    let result = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] >= value) {
            if (nums[mid] === value) {
                result = mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return result;
}

/**
 * Function to find the last occurrence of a value in a sorted array
 * @param {number[]} nums - Sorted array of integers
 * @param {number} value - Value to find
 * @return {number} - Index of the last occurrence
 */
function findLastOccurrence(nums, value) {
    let left = 0;
    let right = nums.length - 1;
    let result = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] <= value) {
            if (nums[mid] === value) {
                result = mid;
            }
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

/**
 * Function to count the number of occurrences of a value in a sorted array
 * @param {number[]} nums - Sorted array of integers
 * @param {number} value - Value to count
 * @return {number} - Number of occurrences
 */
function countOccurrences(nums, value) {
    const first = findFirstOccurrence(nums, value);
    if (first === -1) return 0;

    const last = findLastOccurrence(nums, value);
    return last - first + 1;
}

// Example usage
const nums = [1, 2, 2, 2, 4, 5];
const value = 2;
console.log(countOccurrences(nums, value)); // Output: 3

## Complexity Analysis - **Time Complexity**: O(log n) for both finding the first and last occurrences, resulting in an overall time complexity of O(log n). - **Space Complexity**: O(1) as we are using a constant amount of extra space. ## Edge Cases - **Value Not Present**: If the value is not present in the array, both `findFirstOccurrence` and `findLastOccurrence` will return -1, and the count will be 0. - **All Elements Same**: If all elements in the array are the same as the value, the count will be the length of the array. - **Empty Array**: If the array is empty, the count will be 0. ## Testing To test the solution comprehensively, consider the following test cases: 1. **Basic Test Case**: `nums = [1, 2, 2, 2, 4, 5]`, `value = 2` (Expected output: 3) 2. **Value Not Present**: `nums = [1, 2, 3, 4, 5]`, `value = 6` (Expected output: 0) 3. **All Elements Same**: `nums = [2, 2, 2, 2, 2]`, `value = 2` (Expected output: 5) 4. **Empty Array**: `nums = []`, `value = 2` (Expected output: 0) ## Thinking and Problem-Solving Tips - **Understand Binary Search**: Mastering binary search is crucial for solving problems with O(log n) time complexity. - **Edge Cases**: Always consider edge cases and test your solution against them. - **Practice**: Solve similar problems to improve your problem-solving skills and understanding of algorithms. ## Conclusion In this blog post, we discussed how to count the number of occurrences of a value in a sorted array using binary search. We explored the naive and optimized solutions, provided a detailed algorithm, and implemented the solution in JavaScript. Understanding and solving such problems is essential for efficient data processing and search operations. ## Additional Resources - [Binary Search Algorithm](https://en.wikipedia.org/wiki/Binary_search_algorithm) - [LeetCode Problems on Binary Search](https://leetcode.com/tag/binary-search/) - [GeeksforGeeks Binary Search Tutorial](https://www.geeksforgeeks.org/binary-search/) By practicing and understanding these concepts, you can improve your problem-solving skills and tackle similar challenges effectively.