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 # abs(arr[mid-1]-target) < abs(arr[mid]-target) # abs(arr[mid-1]-target) < abs(arr[mid+1]-target) # 3) the cloest element is on its right side # abs(arr[mid+1]-target) < abs(arr[mid]-target) # abs(arr[mid+1]-target) < abs(arr[mid-1]-target)