Saturday, March 24, 2012

Occurance of key in sorted array.

Given a sorted array and a number n.How can u find the number of occurance of n in the array . should be o(logn)


Approach:
find the lower index of n in array A using binary search.
find the higher index of n in array A using binary search.
total occurances = higher_index-lower_index+1;


code input/output:
printing input array: 
2 3 4 5 5 5 5 6 7 8 
lower index: 3
lower index: 6
Total occurances of key 5: 4

No comments:

Post a Comment