658. 找到 K 个最接近的元素

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # 先二分法找x应该在的位置的索引，再找满足要求的区间。
        n = len(arr) 
        def search_II(x):
            left = 0
            right = n-1
            while left<=right:
                mid = (left+right)>>1
                if arr[mid]>=x:
                    right = mid-1
                elif arr[mid]<x:
                    left = mid+1
            return right+1 
        print("x 的位置是",search_II(x))
        def find_near(index,k):
            left,right = index,index+1
            nearest = []
            arr.insert(0,-10**8)     # 加个左侧哨兵
            arr.append(10**8)        # 加个右侧哨兵
            for i in range(k):            # 循环k次，每一次找一个最近的点。
                if  x-arr[left]<=arr[right]-x: # 往左找一个
                    nearest += [arr[left]] 
                    left -= 1                
                elif arr[right]-x < x-arr[left]: # 往右找一个
                    nearest += [arr[right]]
                    right += 1
            return sorted(nearest)

        x_index = search_II(x)
        return find_near(x_index,k)