K Closest Numbers In Sorted Array

Given a target number, a non-negative integerkand an integer array A sorted in ascending order, find the k closest numbers to target in A, sorted in ascending order by the difference between the number and target. Otherwise, sorted in ascending order by number if the difference is same.

Example

Given A =[1, 2, 3], target =2and k =3, return[2, 1, 3].

Given A =[1, 4, 6, 8], target =3and k =3, return[4, 1, 6].

Solution:

Find the first number that is bigger than target value (or last value if all smaller than target value). Then use two pointers to go left or right depending on which value is closer to target value.

public int[] kClosestNumbers(int[] A, int target, int k) {
    int[] result = new int[k];
    if (k == 0 || k > A.length) {
        return result;
    }
    int index = 0,
        left  = 0,
        right = A.length - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (A[mid] > target) {
            right = mid;
        } else {
            left = mid;
        }
    }
    int closestIndex = A.length;
    if (A[left] >= target) {
        closestIndex = left;
    }
    if (A[right] >= target) {
        closestIndex = right;
    }
    //go left or right depending on which value is closer to target.
    int goLeft  = closestIndex - 1,
        goRight = closestIndex;
    while (index < result.length) {
        if (goLeft < 0) {
            result[index] = A[goRight];
            goRight++;
        } else if (goRight >= A.length) {
            result[index] = A[goLeft];
            goLeft--;
        } else {
            if (Math.abs(A[goLeft] - target) > Math.abs(A[goRight] - target)) {
                result[index] = A[goRight];
                goRight++;
            } else {
                result[index] = A[goLeft];
                goLeft--;
            }
        }
        index++;
    }
    return result;
}