K Closest Numbers In Sorted Array

Given a target number, a non-negative integer k and 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 = 2 and k = 3, return [2, 1, 3].

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

Notes:

1. Binary search to find the closest one
2. Merge from two sides of the closest position
3. Use helper functions, be careful about the corner cases (k==0)

    public int[] kClosestNumbers(int[] A, int target, int k) {
        if (A == null || A.length == 0 || k == 0) {
            return new int[0];
        }

        int pos = findClosestPostion(A, target);

        List<Integer> result = collectKClosestNumbers(A, pos, target, k);

        return changeListToArray(result);
    }

    private int findClosestPostion(int[] A, int target) {
        int start = 0;
        int end = A.length-1;
        while(start+1 < end) {
            int middle = start + (end-start)/2;
            if (A[middle] == target) {
                return middle;
            }

            if (A[middle] < target) {
                start = middle;
            } else {
                end = middle;
            }
        }

        if (Math.abs(A[start] - target) <= Math.abs(A[end]-target)) {
            return start;
        }
        return end;
    }

    private List<Integer> collectKClosestNumbers(int[] A, int pos, int target, int k) {
        List<Integer> result = new ArrayList<>();
        result.add(A[pos]);

        int i = pos-1;
        int j = pos+1;
        while (j-i <= k) {
            int left = Integer.MAX_VALUE;
            if (i >= 0) {
                left = Math.abs(target - A[i]);
            }

            int right = Integer.MAX_VALUE;
            if (j < A.length) {
                right = Math.abs(target-A[j]);
            }

            if (left > right) {
                result.add(A[j]);
                j++;
            } else {
                result.add(A[i]);
                i--;
            }
        }

        return result;
    }

    private int[] changeListToArray(List<Integer> list) {
        int[] answer = new int[list.size()];
        for (int i = 0; i < answer.length; ++i) {
            answer[i] = list.get(i);
        }

        return answer;
    }