Frequency In A Sorted Array

Notes.md

Question: Frequency In A Sorted Array

Intution:

Time Complexity: $$O(log(n))$$

Space Complexity: $$O(1)$$

Solution:

public class Solution {
	public static int countOccurrences(int[] arr, int x) {
		int n = arr.length;
		return upperBound(arr, x, n) - lowerBound(arr, x, n);
	}

	public static int lowerBound(int[] arr, int x, int n) {
        int low = 0;
        int high = n - 1;
        int ans = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < x) low = mid + 1;
            else {
                ans = mid;
                high = mid - 1;
            }
        }
        return ans;
    }
	
	public static int upperBound(int[] arr, int x, int n){
        int low = 0;
        int high = n - 1;
        int ans = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= x) low = mid + 1;
            else {
                ans = mid;
                high = mid - 1;
            }
        }
        return ans;
    }
}