|
This post is completed by 1 user
|
Add to List |
53. Count occurrences of a number in a sorted array
Objective: Given a sorted array of integers, find out the number of occurrences of a number in that array
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(log)
Steps:
- Find the first occurrence of x in the array. say it is startPoint.
- Find the last occurrence of x in the array, say it is endPoint.
- Calculate the number of occurrences = 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 before 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.
No of Occurrences of number 2 is : 7