Thursday, October 17, 2013

Finding a number in a sorted array with the least difference from given number

Given a sorted array and a value, we have to find the closest value (with least difference).

For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11.

This problem is actually a variation of binary search where in we have to find out the closest value found the array. If the given value exists in the array, we have to return that.

A sorted array and binary search gives a hint that we can solve this problem in O( log n) complexity. Here is how we can modify the binary search algorithm to solve this problem.

As in binary search algorithm, we try to search for the given number in the middle of the array. If the element is found, we just return it, because we got the least difference i.e 0.

We also maintain two variables one to store the minimum difference found so far (minDiff), and the other (result) to store the corresponding number. In each iteration, we find the difference between the given value and middle value. If this is lesser than minimum difference, we update the two variables.

At the end of the search we have the required number in the result variable.

Below is the Java code which implements the above algorithm.