Problem

Given a sorted array and a number. Find the element in the array that has minimum difference with the given number.

Example

Example 1:

Input: a[] = [2, 5, 10, 12, 15], target = 6
Output: 5
Explanation: The difference between the target value '6' and '5' is the minimum.

Example 2:

Input: a[] = [2, 5, 10, 12, 15], target = 5
Output: 5

Example 3:

Input: a[] = [2, 5, 10, 12, 15], target = 8
Output: 10

Example 4:

Input: a[] = [2, 5, 10, 12, 15], target = 11
Output: 10

Example 5:

Input: a[] = [2, 5, 10, 12, 15], target = 20
Output: 15

Solution

Method 1 - Using Floor and Ceil of Target

We already have solved these two problem:

If we find the floor and ceiling of the target value in the array, then we can easily find the element that has the minimum difference with the target value.

The element with minimum difference is equal to the minimum of target-floor and ceiling-target.

Method 2 - Using Modified Binary Search

If you analyze the Binary Search on Sorted Array algorithm carefully, then you will find that at the end of the loop, the start and end indices point to the numbers that are closest to the target value being searched for. So essentially, at the end of the loop, the start index points to the ceiling of the target and the end index points to the floor of the target value.

So to find the minimum difference element, we will apply standard binary search and try to search for the target value in the given array. If we find the target, then we return it as the minimum difference element.

If we can’t find the target, then at the end of the loop, we can find the differences between the target and the numbers at indices start and end, as these two numbers will be closest to the target. The number that gives the minimum difference will be the output.

To find the element with the minimum difference to x in a sorted array, we can effectively use binary search to narrow down the closest candidates. By leveraging the sorted property of the array, we can find the element efficiently.

Here are the steps:

  1. Use binary search to find the position where x would be inserted in the array.
  2. Compare the element at this position and its neighboring elements to determine the closest element.
  3. Return the element with the smallest absolute difference to x.

Code

Java
public class Solution {
    public int findClosestElement(int[] arr, int x) {
        int start = 0, end = arr.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (arr[mid] == x) {
                return arr[mid];
            } else if (arr[mid] < x) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        // After binary search, start points to the first element greater than
        // x, and end points to the last element less than x Compare arr[start]
        // and arr[end] to find the closest element
        if (start >= arr.length) {
            return arr[end];
        }
        if (end < 0) {
            return arr[start];
        }
		/* After the while loop, 
		a[start] represents the ceiling of target (the smallest number larger than target), 
		and a[end] represents the floor of target (the largest number smaller than target). 
		Return the number with the smallest difference to target. */
        if (Math.abs(arr[start] - x) < Math.abs(arr[end] - x)) {
            return arr[start];
        } else {
            return arr[end];
        }
    }
}

static int binarySearchMinDifference(int[] a, int target) {
	int n = a.length;

	if (target < a[0])
		return a[0];
	if (target > a[n - 1])
		return a[n - 1];

	int start = 0, end = n - 1;
	while (start <= end) {
		int mid = (start + end) / 2;

		if (target == a[mid]) {
			return a[mid];
		} else if (target < a[mid]) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}

	/*
	   At the end of the while loop, 
	   a[start] is the ceiling of target (Smallest number greater than target), and 
	   a[end] is the floor of target (Largest number smaller than target).
	   
	   Return the element whose difference with target is smaller
	 */
 
	if ((a[start] - target) < (target - a[end]))
		return a[start];
	return a[end];
}
Python
def find_closest_element(arr, x):
    start, end = 0, len(arr) - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:
            return arr[mid]
        elif arr[mid] < x:
            start = mid + 1
        else:
            end = mid - 1

    # After binary search, start points to the first element greater than x, and end points to the last element less than x
    # Compare arr[start] and arr[end] to find the closest element
    if start >= len(arr):
        return arr[end]
    if end < 0:
        return arr[start]

    if abs(arr[start] - x) < abs(arr[end] - x):
        return arr[start]
    else:
        return arr[end]

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)