Data Structures and Algorithms in Python/

...

/

Find the Closest Number

Find the Closest Number

In this lesson, you will learn how to find the closest number to a target number in Python.

We'll cover the following...

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:

Implementation

Here we used the idea in the slides above to come up with a solution. Check it out below:

Press + to interact
A1 = [1, 2, 4, 5, 6, 6, 8, 9]
A2 = [2, 5, 6, 7, 8, 8, 9]
def find_closest_num(A, target):
    min_diff = min_diff_left = min_diff_right = float("inf")
    low = 0
    high = len(A) - 1
    closest_num = None
    # Edge cases for empty list of list
    # with only one element:
    if len(A) == 0:
        return None
    if len(A) == 1:
        return A[0]
    while low <= high:
        mid = (low + high)//2
        # Ensure you do not read beyond the bounds
        # of the list.
        if mid+1 < len(A):
            min_diff_right = abs(A[mid + 1] - target)
        if mid > 0:
            min_diff_left = abs(A[mid - 1] - target)
        # Check if the absolute value between left
        # and right elements are smaller than any
        # seen prior.
        if min_diff_left < min_diff:
            min_diff = min_diff_left
            closest_num = A[mid - 1]
        if min_diff_right < min_diff:
            min_diff = min_diff_right
            closest_num = A[mid + 1]
        # Move the mid-point appropriately as is done
        # via binary search.
        if A[mid] < target:
            low = mid + 1
        elif A[mid] > target:
            high = mid - 1
            if high < 0:
                return A[mid]
        # If the element itself is the target, the closest
        # number to it is itself. Return the number.
        else:
            return A[mid]
    return closest_num
print(find_closest_num(A1, 11))
print(find_closest_num(A2, 4))

Explanation

A is the input array, and target ...