Find the minimum difference element in a sorted array

Given an array of integers sorted in ascending order, and a target value, find the element in the array that has minimum difference with the target value.

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

Binary Search to find the minimum difference element with the given target value in a sorted array

Solution approach using existing problems

This problem is a variation of some of the existing problems we solved using binary search -

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.

Alternate solution approach

If you analyze the binary search 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 minimum difference will be the output.

import java.util.Scanner;

class MinimumDifferenceElementInSortedArray {

    private 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];
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }
        int target = keyboard.nextInt();
        keyboard.close();

        System.out.printf("MinimumDifferenceElementWith(%d) = %d%n", target, binarySearchMinDifference(a, target));
    }
}

# Output
$ javac MinimumDifferenceElementInSortedArray.java
$ java MinimumDifferenceElementInSortedArray
5
2 5 10 12 15
6
MinimumDifferenceElementWith(6) = 5


$ java MinimumDifferenceElementInSortedArray
5
2 5 10 12 15
5
MinimumDifferenceElementWith(5) = 5


$ java MinimumDifferenceElementInSortedArray
5
2 5 10 12 15
8
MinimumDifferenceElementWith(8) = 10


$ java MinimumDifferenceElementInSortedArray
5
2 5 10 12 15
11
MinimumDifferenceElementWith(11) = 10


$ java MinimumDifferenceElementInSortedArray
5
2 5 10 12 15
20

Binary Search