Friday, November 9, 2012

Find the number or next smallest number


 In a sorted array, find if a given number 'X' is found.
 If found, print it
 If not found, print the next smallest number lesser than the given number
 Eg. {17,32,58,60,63,91}
 Num = 35
 Answer = 32

Approach
As the numbers are already sorted, we can use a modified version of binary search. The twist here is, when the middle number is less than 'X' then check if the next number is greater than 'X'.

Alternatively, what if the numbers were not sorted??
Use a min-heap and get the minimum till finding a number greater than 'X'.

Solution

No comments:

Post a Comment

UA-36403895-1