Find the value nearest to k in the sorted array Given a sorted array, return the 'closest' element to the input 'x'.


I do understand the merits of unit testing in separate files, but I deliberately added it to the main method for personal convenience, so don't consider that in your feedback.

I'm looking for request code review, optimizations and best practices.

public final class ClosestToK {

    private ClosestToK() { }

    /**
     * Given a sorted array returns the 'closest' element to the input 'x'.
     * 'closest' is defined as Math.min(Math.abs(x), Math.abs(y)) 
     * 
     * Expects a sorted array, and if array is not sorted then results are unpredictable.
     * 
     * If two values are equi-distant then the greater value is returned.
     * 
     * @param a  The sorted array a
     * @return   The nearest element
     */
    public static int getClosestK(int[] a, int x) {

        int low = 0;
        int high = a.length - 1;

        while (low &lt;= high) {
            int mid = (low + high) / 2;

            // test lower case
            if (mid == 0) {
                if (a.length == 1) {
                    return a[0];
                }

                return Math.min(Math.abs(a[0] - x), Math.abs(a[1] - x)) + x;
            }


            // test upper case
            if (mid == a.length - 1) {
                return a[a.length - 1];
            }

            // test equality
            if (a[mid] == x || a[mid + 1] == x) {
                return x;
            }


            // test perfect range.
            if (a[mid] &lt; x  &amp;&amp; a[mid + 1] &gt; x) {
                return Math.min(Math.abs(a[mid] - x), Math.abs(a[mid + 1] - x)) + x;
            }

            // keep searching.
            if (a[mid] &lt; x) {
                low = mid + 1;
            } else { 
                high = mid;
            }
        }

        throw new IllegalArgumentException("The array cannot be empty");
    }


    public static void main(String[] args) {
        // normal case.
        int[] a1 = {10, 20, 30, 40};
        assertEquals(30, getClosestK(a1, 28));

        // equidistant
        int[] a2 = {10, 20, 30, 40};
        assertEquals(30, getClosestK(a2, 25));

        // edge case lower boundary
        int[] a3 = {10, 20, 30, 40};
        assertEquals(10, getClosestK(a3, 5));
        int[] a4 = {10, 20, 30, 40};
        assertEquals(10, getClosestK(a4, 10));

        // edge case higher boundary 
        int[] a5 = {10, 20, 30, 40};
        assertEquals(40, getClosestK(a5, 45));
        int[] a6 = {10, 20, 30, 40};
        assertEquals(40, getClosestK(a6, 40));

        // case equal to 
        int[] a7 = {10, 20, 30, 40};
        assertEquals(30, getClosestK(a7, 30));

    }
}
Here's my solution which seems to work fine :

public static int getClosestK(int[] a, int x) {

    int low = 0;
    int high = a.length - 1;

    if (high &lt; 0)
        throw new IllegalArgumentException("The array cannot be empty");

    while (low &lt; high) {
        int mid = (low + high) / 2;
        assert(mid &lt; high);
        int d1 = Math.abs(a[mid  ] - x);
        int d2 = Math.abs(a[mid+1] - x);
        if (d2 &lt;= d1)
        {
            low = mid+1;
        }
        else
        {
            high = mid;
        }
    }
    return a[high];
}


Here's the principle : the interval [low, high] will contain the closest element to x at any time. At the beginning, this interval is the whole array ([low, high] = [0, length-1]). At each iteration, we'll make it strictly smaller. When the range is limited to a single element, this is the element we are looking for.

In order to make the range smaller, at each iteration, we'll consider mid the middle point of [low, high]. Because of the way mid is computed, mid+1 is also in the range. We'll check if the closest value is at mid or mid+1 and update high or low accordingly. One can check that the range actually gets smaller.

Edit to answer to comments:

As spotted by @Vick-Chijwani , this code doesn't handle perfectly the scenarios where an element appears multiple times in the input. One can add the following working tests to the code :

    // case similar elements
    int[] a8 = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10};
    assertEquals(10, getClosestK(a8, 9));
    assertEquals(10, getClosestK(a8, 10));
    assertEquals(10, getClosestK(a8, 11));


but this one will fail :

   int[] a9 = {1, 2, 100, 100, 101};
   assertEquals(3, getClosestK(a9, 2)); // actually returns 100