Find the value nearest to k in the sorted array
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