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
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