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

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 ### Naive Solution A naive solution would involve iterating through the array and counting the occurrences of the given value. This approach has a time complexity of O(n), which is not efficient for large arrays. ### 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 given value. The difference between these indices plus one will give us the count of occurrences. ### Steps to Solve 1. **Find the First Occurrence**: Use binary search to find the first occurrence of the value. 2. **Find the Last Occurrence**: Use binary search to find the last occurrence of the value. 3. **Calculate the Count**: The count of occurrences is the difference between the indices of the last and first occurrences 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 `(left + right) / 2`. - 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]` is equal to 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 `(left + right) / 2`. - If `nums[mid]` is greater than the value, move `right` to `mid - 1`. - If `nums[mid]` is less than or equal to the value, move `left` to `mid + 1`. - If `nums[mid]` is equal to the value, update `result` to `mid` and move `left` to `mid + 1` to find the last occurrence. ## Code Implementation

public class NumberOfOccurrences {
    // Function to find the first occurrence of the value
    public static int findFirstOccurrence(int[] nums, int value) {
        int left = 0, right = nums.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 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 the value
    public static int findLastOccurrence(int[] nums, int value) {
        int left = 0, right = nums.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 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 the value
    public static int countOccurrences(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;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 2, 4, 5};
        int value = 2;
        System.out.println("Number of occurrences of " + value + ": " + countOccurrences(nums, value));
    }
}

## 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, the function should return 0. - **All Elements Same**: If all elements in the array are the same as the value, the function should return the length of the array. - **Empty Array**: If the array is empty, the function should return 0. ## Testing To test the solution comprehensively, consider the following test cases: 1. **Simple Case**: `nums = [1, 2, 2, 2, 4, 5]`, `value = 2` (Expected output: 3) 2. **Value Not Present**: `nums = [1, 3, 4, 5]`, `value = 2` (Expected output: 0) 3. **All Elements Same**: `nums = [2, 2, 2, 2]`, `value = 2` (Expected output: 4) 4. **Empty Array**: `nums = []`, `value = 2` (Expected output: 0) ## Conclusion Understanding and solving this problem helps in mastering binary search and its applications in efficient searching algorithms. Practice similar problems to improve your problem-solving skills and deepen your understanding of binary search. ## Additional Resources - [Binary Search Algorithm](https://en.wikipedia.org/wiki/Binary_search_algorithm) - [LeetCode Binary Search Problems](https://leetcode.com/tag/binary-search/) - [GeeksforGeeks Binary Search](https://www.geeksforgeeks.org/binary-search/) By practicing and exploring further, you can enhance your algorithmic thinking and problem-solving abilities.