Q: Given a sorted array find number of occurrences of a given number
If the interviewer has mentioned that the given array is in sorted array then he is expecting the solution to be in log( n ) time.
We can solve this using binary search. To find the no of occurrences of the given number we can find the first occurrence of the number and the last occurrence of the number and return the difference between them.
To find the first occurrence of a number we need to check for the following condition. Return the position if any of the following is true.
(mid == low && A[mid] == data) || (A[mid] == data && A[mid-1] < data)
To find the last occurrence of a number we need to check for the following condition. Return the position if any of the following is true.
(mid == high && A[mid] == data) || (A[mid] == data && A[mid+1] > data)
http://flexaired.blogspot.com/2011/03/no-of-occurrences-of-number.html
Refer : http://www.geeksforgeeks.org/archives/12164
No comments:
Post a Comment