K Closest Number 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].

分析：

二分法本身不算复杂，后续的逻辑需要好好思考一下。

解法：

class Solution {
public:
    /**
     * @param A an integer array
     * @param target an integer
     * @param k a non-negative integer
     * @return an integer array
     */
    vector<int> kClosestNumbers(vector<int>& A, int target, int k) {
        // Write your code here
        if (A.size() == 0 || k == 0) {
            return vector<int>();
        }
        int start = 0;
        int end = A.size() - 1;

        int mid = 0;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        vector<int> res;

        while (res.size() < k) {

            if (start < 0 && end >= A.size() ) {
                break;
            }

            if (start < 0) {
                res.push_back(A[end]);
                end++;
                continue;
            }

            if (end >= A.size() ) {
                res.push_back(A[start]);
                start--;
                continue;
            }

            if (target - A[start] <= A[end] - target) {
                res.push_back(A[start]);
                start--;
            } else {
                res.push_back(A[end]);
                end++;
            }

        }

        return res;
    }
};