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.

• 使用Binary Search找到最接近的数字的位置

• 双指针从该位置左右移动，每次比较找到最接近的数字，加入到答案中，相应的指针++

class Solution:
    # @param {int[]} A an integer array
    # @param {int} target an integer
    # @param {int} k a non-negative integer
    # @return {int[]} an integer array
    def kClosestNumbers(self, A, target, k):
        # Write your code here
        start, end = 0, len(A) - 1
        index = 0
        while start + 1 < end:
            mid = (start + end) / 2
            if A[mid] < target:
                start = mid
            else:
                end = mid
        if target<=A[start]:
            index = start
        elif target >= A[end]:
            index = end
        else:
            if target-A[start] >=A[end]-target:
                index = end
            else:
                index = start
        left = index - 1
        right = index
        result = []
        for i in range(1,k+1):
            # 先判断left，因为left是index－1
            if left<0:
                result.append(A[right])
                right += 1
            # 这里用elif，不用if，因为判断完left<0会加到result里一个数字，
            # 不能在用if判断right， 每一次for loop只能加进去一个数字，
            # 否则最后result里面会超出k个数字
            elif right > len(A)-1:
                result.append(A[left])
                left -= 1
            else:
                if target-A[left] >A[right]-target:
                    result.append(A[right])
                    right+=1
                else:
                    result.append(A[left])
                    left -= 1
        return result