Find the Minimum Difference Element in a Sorted Array - Java Solution

1. Introduction

This blog post explores how to find the element in a sorted array that has the minimum difference with a given target value. This problem is an interesting application of binary search where we aim to minimize the difference rather than finding an exact match.

Problem

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

Example 1:

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

Output: 5

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

2. Solution Steps

1. Apply binary search to find the closest element to the target.

2. Keep track of the minimum difference and the element associated with this minimum difference.

3. Compare the target with elements at mid, mid - 1, and mid + 1 to find the closest match.

4. Return the element with the minimum difference to the target.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a = {2, 5, 10, 12, 15};
        System.out.println("Minimum difference element for 6: " + findMinDiffElement(a, 6));
        System.out.println("Minimum difference element for 5: " + findMinDiffElement(a, 5));
        System.out.println("Minimum difference element for 8: " + findMinDiffElement(a, 8));
        System.out.println("Minimum difference element for 11: " + findMinDiffElement(a, 11));
        System.out.println("Minimum difference element for 20: " + findMinDiffElement(a, 20));
    }

    // Method to find the element with the minimum difference
    public static int findMinDiffElement(int[] a, int target) {
        int start = 0, end = a.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (a[mid] == target) {
                return a[mid];
            }

            if (mid > 0 && a[mid - 1] <= target && target < a[mid]) {
                return getClosest(a[mid - 1], a[mid], target);
            }

            if (mid < a.length - 1 && a[mid] < target && target <= a[mid + 1]) {
                return getClosest(a[mid], a[mid + 1], target);
            }

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

    // Helper method to find the closest of two numbers to the target
    private static int getClosest(int val1, int val2, int target) {
        if (target - val1 >= val2 - target) {
            return val2;
        }
        return val1;
    }
}

Output:

Minimum difference element for 6: 5
Minimum difference element for 5: 5
Minimum difference element for 8: 10
Minimum difference element for 11: 10
Minimum difference element for 20: 15

Explanation:

The findMinDiffElement method applies a modified binary search to find the closest element to the target. It checks the elements at mid, mid - 1, and mid + 1 to determine the closest match. 

For example, for the input array [2, 5, 10, 12, 15] and target 6, it finds that 5 is the closest element to 6 with the minimum difference. 

The method efficiently finds the closest element with minimal difference from the target, adhering to the constraints of the problem.