# Find the number of occurrences of a number in a given sorted array.

Objective: Given a sorted(ascending order) arrays of integers, find out the number of occurences of a number in that array

Input: A sorted array arrA[] and a number x.

Output: number of occurrences of ‘x’ in array arrA[].

Examples :

```Array - {1,2,2,2,2,2,2,2,3,4,5,5,6}
x = 2
Output : No of Occurrences of number 2 is 7
```

Approach:

Method 1: O(n)

Do the linear scan and count the occurrences.

Method 2: Binary search Technique : O(lgn)

Steps:

• Find the first occurrence of x in the array. say it is startPoint.
• Find the last occurrrence of x in the array, say it is endPoint.
• Calculate the number of occurrence = endPoint-startPoint+1

How do you find the first occurrence of a number using binary search.

Put one additional condition in the step when array[mid]==x, just check whether the element prior to mid is smaller than the x, if yes then only return the mid index, this will give you the first occurrence. handle the boundary conditions.

How do you find the last occurrence of a number using binary search.

Put one additional condition in the step when array[mid]==x, just check whether the element after the mid is greater than the x, if yes then only return the mid index, this will give you the last occurrence. handle the boundary conditions.

Complete Code:

 public class OccurrencesInArray { public int findOccurrences(int [] arrA, int x){ int count = 0; int startPoint = findFirstOccurrence(arrA,x,0,arrA.length–1); if(startPoint<0){ return –1; } int endPoint = findLastOccurrence(arrA, x, 0, arrA.length–1); count = endPoint–startPoint+1; return count; } public int findFirstOccurrence(int [] arrA, int x,int start, int end ){ if(end>=start){ int mid = (start+end)/2; if((mid==0||(arrA[mid–1]=start){ int mid = (start+end)/2; if((mid==arrA.length–1||arrA[mid+1]>x) &&(arrA[mid]==x)){ return mid; }else if(arrA[mid]>x){ return findLastOccurrence(arrA, x, start, mid–1); }else{ return findLastOccurrence(arrA, x, mid+1, end); } }else return –1; } public static void main(String args[]){ int [] arrA = {1,2,2,2,2,2,2,2,3,4,5,5,6}; int x = 2; OccurrencesInArray i = new OccurrencesInArray(); int r = i.findOccurrences(arrA, x); System.out.println("No of Occurrences of number " + x + " is : " + r); } }

Output:

`No of Occurrences of number 2 is : 7`