题目：

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
 

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：

输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]
 

提示：

1 <= k <= arr.length
1 <= arr.length <= 104
arr 按 升序 排列
-104 <= arr[i], x <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-k-closest-elements
 

思路：

1. 使用二分法查找目标 x 在数组中应该插入的位置 index, 此时说明：要求的k个数在 下标为 index - k +1 到  index + k -1 之间
2. 利用双指针：令 left = index - k +1, right = index + k -1；
3. 当 right - left + 1 > k 时，如果 abs (nums[left] - x) > abs(nums[right] - x), 则左边界右移；如果 abs (nums[left] - x) <= abs(nums[right] - x), 则右边界左移；直到 right - left + 1 == k 为止

java代码如下：

class Solution {public List findClosestElements(int[] arr, int k, int x) {int left = 0;int right = arr.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (arr[mid] < x) {left = mid + 1;} else {right = mid;}}int x_index = left;int left_index = Math.max(x_index - k, 0);int right_index = Math.min(x_index + k, arr.length - 1);while (right_index - left_index + 1> k) {if (Math.abs(x - arr[left_index]) > Math.abs(x - arr[right_index])) {left_index++;} else {right_index--;}}List result = new ArrayList<>();for (int i = left_index; i <= right_index; i++) {result.add(arr[i]);   }return result;}
}

c++

class Solution {
public:vector findClosestElements(vector& arr, int k, int x) {int L = 0;int R = arr.size() - 1;while(L < R) {int mid = L + (R - L)/2;if(arr[mid] < x) {L = mid + 1;} else {R = mid;}}int left = (R-k)>=0 ? (R-k):0;int right = (R+k) <= (arr.size()-1)? (R+k):(arr.size()-1);while(right - left + 1 > k) {int left_v = (x - arr[left]) >= 0 ? (x - arr[left]) : (arr[left] - x);int right_v = (x - arr[right]) >= 0 ? (x - arr[right]) : (arr[right] - x);// 当 abs (arr[left] - x) == abs(arr[right] - x) 时，此时应该保留更小的 arr[left] , 即将 right 左移if(left_v <= right_v) {right--;} else {left++;}}vector result;for(int i=left;i<=left+k-1;i++) {result.emplace_back(arr[i]);}return result;}
};