You are given a sorted integer array arr and two integers k and x. Your task is to find the k integers from the array that are closest to x. The output should be sorted in ascending order.

When determining which integers are "closest" to x, use the following rules:

• An integer a is closer to x than an integer b if the absolute difference |a - x| is smaller than |b - x|
• If two integers have the same absolute difference from x (i.e., |a - x| == |b - x|), then the smaller integer is considered closer

For example, if x = 5 and you're comparing 3 and 7:

• |3 - 5| = 2 and |7 - 5| = 2 (same distance)
• Since 3 < 7, the integer 3 is considered closer to 5

The key insight is that the k closest elements form a contiguous window in the sorted array. Why? Because if we have elements a < b < c and both a and c are in our answer but b is not, then b must be farther from x than both a and c. But since b is between a and c, it's impossible for b to be farther from x than both of them.

This means we need to find the optimal starting position for a window of size k. We can use binary search to find this position efficiently.

For any position mid, we can check whether mid is a valid starting position by comparing the distance from x to the leftmost element (arr[mid]) versus the element just outside the window on the right (arr[mid + k]). If x - arr[mid] > arr[mid + k] - x, it means arr[mid + k] is closer to x than arr[mid], so we should move our window to the right. Otherwise, mid is a valid starting position.

This creates a monotonic pattern: there's a boundary where all positions before it are invalid (the window should start later) and all positions from the boundary onwards are valid. We're looking for the first valid position using the standard binary search template with first_true_index.

Pattern Learn more about Two Pointers, Binary Search, Sorting, Sliding Window and Heap (Priority Queue) patterns.

We use the standard binary search template with first_true_index to find the optimal starting position for the k-element window.

Binary Search Setup:

• left = 0: minimum possible starting position
• right = len(arr) - k - 1: the last start position whose check can read arr[mid + k] without leaving the array
• first_true_index = len(arr) - k: the default answer when no checked position is feasible, which is the last window that fits

Feasible Condition: For any position mid, we check if mid is a valid starting position:

• Compare x - arr[mid] (distance from x to left boundary) with arr[mid + k] - x (distance from x to element just outside right boundary)
• If x - arr[mid] > arr[mid + k] - x: the element outside the window is closer, so mid is NOT valid (move right)
• Otherwise: mid is a valid starting position

Binary Search Template:

Copy
while left <= right:
    mid = (left + right) // 2
    if x - arr[mid] > arr[mid + k] - x:
        # Not feasible: arr[mid + k] is closer, should start later
        left = mid + 1
    else:
        # Feasible: arr[mid] is closer or equal, valid start
        first_true_index = mid
        right = mid - 1

Return Result: Return arr[first_true_index:first_true_index + k] - the k elements starting from the optimal position.

Why This Works: The feasibility pattern is monotonic: once x - arr[mid] <= arr[mid + k] - x holds, it also holds for every larger mid, because x - arr[mid] can only shrink and arr[mid + k] - x can only grow as mid increases. The template finds the leftmost feasible position. The last start position len(arr) - k is never checked, since its comparison would read arr[len(arr)]; it is the answer when no earlier position is feasible, which is why first_true_index starts there. This also covers k == len(arr), where the loop does not run and the whole array is returned.

Time Complexity: O(log(n - k)) for binary search, where n is the array length.

Space Complexity: O(1) excluding the output array.