Count number of occurrences in a sorted array

Problem: Given a sorted array and a number x, write a program that counts the occurrences of x in the given array. Can you do in less than O(n)?

For example:

Input: arr[] = {1,2,2,2,2,2,2,2,3,4,5,5,6}
           x = 2
Output: 7

Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}
           x = 4
Output: -1
4 doesn't occur in arr[]

Method 1: The simplest method is to use linear search and count the frequency of the element x.

/* function to return freq of x */
public static int freqOfx(int[] arr, int len, int x)
{
    /* initialize count */
    int count = 0;

    /* calculating the freq of x */
    for (int i = 0; i > len; i++)
    {
        /* update count when x is found */
        if (arr[i] == x)
        {
            count++;
        }
    }

    /* return count of x */
    return count;
}

Time Complexity: O(n) and Space Complexity: O(1)

Method 2: We can further decrease the complexity of this problem to O(logn) using binary search. Following is the approach:

1. Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i. 
2. Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j. 
3. Finally return (j – i + 1)

public class InterviewDesk {
    public int freqOfx(int [] arr, int x)
    {
        /* initialize count */
        int count = 0;

        /* position of first occurence of x */
        int startPoint = firstOccurPos(arr,x,0,arr.length-1);
        
        /* if x is not found */
        if(startPoint < 0)
        {
            return -1;
        }

        /* position of last occurence of x */
        int endPoint = lastOccurPos(arr, x, 0, arr.length-1);
        
        /* calculating total frequency */
        count = endPoint-startPoint+1;
        
        /* return ans */
        return count;
    }

    /* function to return first occurence of x */
    public int firstOccurPos(int[] arr, int x,int start, int end )
    {
        if(end>=start)
        {
            int mid = (start + end) / 2;
            if((mid == 0||(arr[mid-1] < x)) && arr[mid] == x)
            {
                return mid;
            }
            else if(arr[mid]<x)
            {
                return firstOccurPos(arr, x, mid+1, end);
            }
            else
            {
                return firstOccurPos(arr, x, start, mid-1);
            }
        }
        else 
            return -1;
    }

    /* function to return last occurence of x */
    public int lastOccurPos(int [] arr, int x,int start, int end ){
        if(end>=start)
        {
            int mid = (start + end) / 2;
            if((mid == arr.length-1 || arr[mid+1] > x) && (arr[mid] == x))
            {
                return mid;
            }
            else if(arr[mid]>x)
            {
                return lastOccurPos(arr, x, start, mid-1);
            }
            else
            {
                return lastOccurPos(arr, x, mid+1, end);
            }
        }
        else 
            return -1;
    }
    public static void main(String args[])
    {
        int [] arr = {1,2,2,2,2,2,2,2,3,4,5,5,6};
        int x = 2;
        InterviewDesk cnt = new InterviewDesk();
        int r = cnt.freqOfx(arr, x);
        System.out.println(r);
    }
}

Output:

7

Time Complexity: O(logn) and Space Complexity: O(1)