|
Be the first user to complete this post
|
Add to List |
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.
Code:
No of Occurrences of number 2 is : 7
Also Read: