Popular Posts

Sunday, March 20, 2011

No of occurrences of a number in Array


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