给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数.返回的结果必须要是按升序排好的.如果有两个数与 x 的差值一样,优先选择数值较小的那个数.
k 的值为正数,且总是小于给定排序数组的长度.
数组不为空,且长度不超过 104
数组里的每个元素与 x 的绝对值不超过 104
给出一个数组,要求在数组中找到一个长度为 k 的区间,这个区间内每个元素距离 x 的距离都是整个数组里面最小的.
这一题可以用双指针解题,最优解法是二分搜索.由于区间长度固定是 K 个,所以左区间最大只能到 len(arr) - K (因为长度为 K 以后,正好右区间就到数组最右边了),在 [0len(arr) - K] 这个区间中进行二分搜索.如果发现 a[mid] 与 x 距离比 a[mid + k] 与 x 的距离要大,说明要找的区间一定在右侧,继续二分,直到最终 low = high 的时候退出.逼出的 low 值就是最终答案区间的左边界.