Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given a sorted(ascending order) arrays of inte­gers, find out the num­ber of occurences of a num­ber in that array

Input: A sorted array arrA[] and a num­ber x.

Out­put: num­ber of occur­rences of ‘x’ in array arrA[].

Exam­ples :

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 lin­ear scan and count the occurrences.

Method 2: Binary search Tech­nique : O(lgn)

Steps:

  • Find the first occur­rence of x in the array. say it is startPoint.
  • Find the last occur­rrence of x in the array, say it is endPoint.
  • Cal­cu­late the num­ber of occur­rence = endPoint-startPoint+1

How do you find the first occur­rence of a num­ber using binary search.

Put one addi­tional con­di­tion in the step when array[mid]==x, just check whether the ele­ment prior to mid is smaller than the x, if yes then only return the mid index, this will give you the first occur­rence. han­dle the bound­ary conditions.

How do you find the last occur­rence of a num­ber using binary search.

Put one addi­tional con­di­tion in the step when array[mid]==x, just check whether the ele­ment after the mid is greater than the x, if yes then only return the mid index, this will give you the last occur­rence. han­dle the bound­ary conditions.

Com­plete Code:


Out­put:

No of Occurrences of number 2 is : 7

You may also like...