No of occurrences of a number

Q: Given a sorted array find number of occurrences of a given number

If the interviewer has mentioned that the given array is in sorted array then he is expecting the solution to be in log( n ) time.

We can solve this using binary search. To find the no of occurrences of the given number we can find the first occurrence of the number and the last occurrence of the number and return the difference between them.

To find the first occurrence of a number we need to check for the following condition. Return the position if any of the following is true.

(mid == low && A[mid] == data) || (A[mid] == data && A[mid-1] < data)

To find the last occurrence of a number we need to check for the following condition. Return the position if any of the following is true.

(mid == high && A[mid] == data) || (A[mid] == data && A[mid+1] > data)

Working Java Code:

public class NoOfOccurences {

    public static int findFirstOccurence(int A[],int low,int high,int data)
    {
        int mid;
       
        while(low <= high)
        {
            mid = low + (high-low)/2;
            if(( mid == low && A[mid] == data) || (A[mid] == data && A[mid-1] < data))
            {
                return mid;
            }else if(A[mid] >= data)
            {
                high = mid-1;
            }else
            {
                low = mid+1;
            }   
        }
       
        return -1;
       
    }
   
    public static int findLastOccurence(int A[],int low,int high,int data)
    {
        int mid;
       
        while(low <= high)
        {
            mid = low + (high-low)/2;
            if(( mid == high && A[mid] == data) || (A[mid] == data && A[mid+1] > data))
            {
                return mid;
            }else if(A[mid] <= data)
            {
                low = mid+1;
            }else
            {
                high = mid-1;
            }   
        }
       
        return -1;
    }
    
    
    public static void main(String[] args) {
        int a[] = {1,2,3,3,3,3,4,5,6};
        int firstCount = NoOfOccurences.findFirstOccurence(a,0,8,3);
        int lastCount = NoOfOccurences.findLastOccurence(a,0,8,3);
       
        int noOfOccur = (lastCount - firstCount) +1;
        System.out.print("No of occurences"+noOfOccur);

    }

}