## 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``````