Python - Standard Binary Search
IntuitionBinary search allows us to see what index x should be at. We can then create a sliding window around x of the k closest elements.Approach 1
Use binary
# Intuition
Binary search allows us to see what index `x` should be at. We can then create a sliding window around `x` of the `k` closest elements.

# Approach 1
1. Use binary search to find index `xInd` where `x` would be in the list
2. Set `leftPtr = xInd` and `rightPtr = xInd + 1`
3. Repeat `k` times:
    a. If `arr[leftPtr] <= arr[rightPtr]`, then append `arr[leftPtr]` and decrement `leftPtr`
    b. Otherwise, append `arr[rightPtr]` and increment `rightPtr`
4. Sort the final list

# Complexity
- Time complexity:
$$O(\log(n) + k \log(k))$$

- Space complexity:
$$O(k)$$ extra space

# Code
```python3 []
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        xInd = self.binSearch(arr, x)
        
        leftPtr = xInd
        rightPtr = xInd + 1
        out = []

        for i in range(k):
            if leftPtr < 0:
                out.append(arr[rightPtr])
                rightPtr += 1
            elif rightPtr >= len(arr):
                out.append(arr[leftPtr])
                leftPtr -= 1
            else:
                leftDist = abs(arr[leftPtr] - x)
                rightDist = abs(arr[rightPtr] - x)
                
                if leftDist <= rightDist:
                    out.append(arr[leftPtr])
                    leftPtr -= 1
                else:
                    out.append(arr[rightPtr])
                    rightPtr += 1
        
        return sorted(out)

    # Find index where x would be in arr
    def binSearch(self, arr, x):
        low = 0
        high = len(arr) - 1
        while low < high:
            mid = (low + high) // 2
            if arr[mid] == x:
                return mid
            elif arr[mid] < x:
                low = mid + 1
            else:
                high = mid
        return low - 1
```

# Approach 2
This is the same as Approach 1, except we use a `deque` instead of a list. Using the deque, we don't have to sort the list at the end. Instead, when handling `arr[leftPtr]` and `arr[rightPtr]`, just insert `arr[leftPtr]` at the beginning of the deque, and `arr[rightPtr]` at the end of the deque.

# Complexity
- Time complexity:
$$O(\log(n) + k)$$

- Space complexity:
$$O(k)$$ extra space

# Code
```python3 []
from collections import deque
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        xInd = self.binSearch(arr, x)
        
        leftPtr = xInd
        rightPtr = xInd + 1
        out = deque()

        for i in range(k):
            if leftPtr < 0:
                out.append(arr[rightPtr])
                rightPtr += 1
            elif rightPtr >= len(arr):
                out.appendleft(arr[leftPtr])
                leftPtr -= 1
            else:
                leftDist = abs(arr[leftPtr] - x)
                rightDist = abs(arr[rightPtr] - x)
                
                if leftDist <= rightDist:
                    out.appendleft(arr[leftPtr])
                    leftPtr -= 1
                else:
                    out.append(arr[rightPtr])
                    rightPtr += 1

        return list(out)

    # Find index where x would be in arr
    def binSearch(self, arr, x):
        low = 0
        high = len(arr) - 1
        while low < high:
            mid = (low + high) // 2

            if arr[mid] == x:
                return mid
            elif arr[mid] < x:
                low = mid + 1
            else:
                high = mid
        return low - 1
```

Note: Approach 1 will often run faster than Approach 2, even though it has worse time complexity (since `deque`s in Python are relatively slow compared to lists).
['Binary Search', 'Python3']