658. Find K Closest Elements

class solution: def findCloestElements(self, arr, k, x): """ arr is sorted """ # first find the closest one element. left = 0 right = len(arr)-1 mid = (left+right) // 2 # when length is even, real middle will be a .5, and our mid will be on the left side of that element. # when length is odd, the arr[mid] is the actual mid element. # there are three possibilities: # 1) arr[mid] is the cloeset element # arr[mid] - target == 0 # abs(arr[mid] - target) < abs(arr[mid+1] - target) we assume no duplicates # abs(arr[mid] - target) < abs(arr[mid-1] - target) # 2) the cloest element is on its left side # 3) the cloest element is on its right side # Note here we assume the length of the arr is at least 3 # if arr[mid]-target is smallest, we return arr[mid] # if arr[mid-1]-target is the smallest, we need to continue searching the left. e.g. can arr[mid-2]-target still smaller? # if arr[mid+1]-target is the smallest, we need to continue searching the right. e.g. can arr[mid+2]-target still smaller? arr[mid]