Pick the K Values Nearest a Target in a Sorted Integer Array

You are given an integer array arr sorted in non-decreasing order, an integer k, and a target integer x. Return the k elements of arr that are closest to x, listed in ascending order.

Function Signature

def nearest_values(arr: list[int], k: int, x: int) -> list[int]:

Rules

• Element a is closer to x than element b when abs(a - x) < abs(b - x), or when abs(a - x) == abs(b - x) and a < b. On an exact tie in distance, the smaller value wins.
• arr may contain duplicates. Each array position is a separate element, so a repeated value can appear in the output as many times as it is selected.
• x does not need to be present in arr and may lie below its smallest or above its largest value.
• Return the selected elements sorted in non-decreasing order.

Constraints

• 1 <= k <= len(arr) <= 10^4
• arr is sorted in non-decreasing order
• -10^4 <= arr[i], x <= 10^4

Examples

Example 1

arr = [1, 3, 4, 7, 9], k = 2, x = 5
output = [3, 4]

4 is 1 away from the target. 3 and 7 are both 2 away, and the tie goes to the smaller value, 3.

Example 2

arr = [2, 4, 6, 8], k = 3, x = 10
output = [4, 6, 8]

The target lies past the end of the array, so the three largest values are the closest.

Example 3

arr = [-3, -1, -1, 2, 5], k = 3, x = 0
output = [-1, -1, 2]

Both copies of -1 are 1 away, and 2 is 2 away, which beats -3 (3 away) and 5 (5 away).