Find the Closest Number

In this lesson, we will be given a sorted array and a target number. Our goal is to find a number in the array that is closest to the target number. We will be making use of a binary search to solve this problem, so make sure that you have gone through the previous lesson.

The array may contain duplicate values and negative numbers.

Below are some examples to help you understand the problem:

Example 1

    Input : arr[] = {1, 2, 4, 5, 6, 6, 8, 9}
    Target number = 11
    Output : 9
    9 is closest to 11 in given array

Example 2

    Input :arr[] = {2, 5, 6, 7, 8, 8, 9};
    Target number = 4
    Output : 5

Now the intuitive approach to solving this problem is to iterate through the array and calculate the difference between each element and the target element. The closest to target will be the element with the least difference. Unfortunately, the running time complexity for this algorithm will increase in proportion to the size of the array. We need to think of a better approach.

Algorithm

Have a look at the slides below to get an idea of what we are about to do: