Find K Closest Elements

https://leetcode.com/problems/find-k-closest-elements/

• Naive

def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
    L = sorted([(abs(elt - x), elt) for elt in arr], key=lambda tup: tup[0])
    return sorted([tup[1] for tup in L[:k]])

• Opti

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - k
        
        while left < right:
        
            mid = (left + right) // 2
            if x > (arr[mid] + arr[mid + k])//2):
                left = mid + 1
            else:
                right = mid
        
        return arr[left: left + k]