LC 0658 [M] Find K Closest Elements - ALawliet/algorithms GitHub Wiki

first binary search

x - A[mid] <= A[mid + k] - x, need to move window go left (r = m)
case 1: outside left
-------(x)----A[mid]-----------------A[mid + k]----------

case 2: inside left is smaller:
-------A[mid]----(x)-----------------A[mid + k]----------

*** x - A[mid] > A[mid + k] - x, need to move window go right *** (l = m + 1)
case 3: inside left
-------A[mid]------------------(x)---A[mid + k]----------

case 4: outside right
-------A[mid]---------------------A[mid + k]----(x)------

since k < len(A) we can use len(A) - k as max search space

class Solution:
    def findClosestElements(self, A: List[int], k: int, x: int) -> List[int]:
        l = 0
        r = len(A) - k
        while l < r:
            m = (l + r) // 2
            dist_x_to_l = x - A[m]
            dist_r_to_x = A[m+k] - x
            if dist_x_to_l > dist_r_to_x:
                l = m + 1
            else:
                r = m
        return A[l:l+k]

class Solution:
    def findClosestElements(self, A: List[int], k: int, x: int) -> List[int]:
        l = 0
        r = len(A) - k
        while l < r:
            m = (l + r) // 2
            dist_l_to_x = abs(A[m] - x)
            dist_r_to_x = A[m+k] - x
            if dist_l_to_x > dist_r_to_x:
                l = m + 1
            else:
                r = m
        return A[l:l+k]