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:

Output:

No of Occurrences of number 2 is : 7

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: