Leetcode 658 Find K Closest Elements

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or |a - x| == |b - x| and a < b

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

• We can utilize binary search to find the index s which makes both s and s + k have almost the same difference to x. In each iteration, if mid + k is closer to x, it means elements from mid + 1 to mid + k are all equal or closer to x due to ascending order. Thus we can discard mid by assigning left to mid + 1. Otherwise, it means mid is equal or closer to x than mid + k so we remain mid in next comparison. In the end, we will found an index s that has the balanced range with s + k.
• neetcode gözden geçir.

class Solution:
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """

        # approach: use binary search to find the start which is closest to x

        left = 0
        right = len(arr) - k

        while left < right:
            mid = left + (right - left) // 2

            # mid + k is closer to x, discard mid by assigning left = mid + 1
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1

            # mid is equal or closer to x than mid + k, remains mid as candidate
            else:
                right = mid

        # left == right, which makes both left and left + k have same diff with x
        return arr[left : left + k]