> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/7.two-pointers/658.-find-k-closest-elements-m.md).

# 658. Find K Closest Elements (M)

Given a **sorted** integer array `arr`, two integers `k` and `x`, return the `k` closest integers to `x` in the array. The result should also be sorted in ascending order.

An integer `a` is closer to `x` than an integer `b` if:

* `|a - x| < |b - x|`, or
* `|a - x| == |b - x|` and `a < b`

**Example 1:**

```
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
```

**Example 2:**

```
Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]
```

&#x20;

**Constraints:**

* `1 <= k <= arr.length`
* `1 <= arr.length <= 104`
* `arr` is sorted in **ascending** order.
* `-104 <= arr[i], x <= 104`

### Solution:

直接在数组中二分查找 `target`, 如果不存在则返回大于 `target` 的最小的或者小于 `target` 的最大的元素均可.

然后使用两根指针从该位置开始向两端遍历, 每次把差值比较小的元素放入答案中然后将该指针向边界方向移动一下即可

```
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        
        int left = findLowerClosest(arr, x);
        int right = left+1;
        int[] result = new int[k];
        for(int i = 0; i< k;i++)
        {
            if(left < 0)
            {
                result[i] = arr[right++];
            }
            else if(right >= arr.length)
            {
                result[i] = arr[left--];
            }else
            {
                 if(x - arr[left] <= arr[right] - x)
                {
                    result[i] = arr[left];
                    left--;
                }
                else
                {
                    result[i] = arr[right];
                    right++;
                }  
            }   
        }
        
        Arrays.sort(result);
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i< k;i++)
        {
            list.add(result[i]);
        }
        return list;
    }
    
    public int findLowerClosest(int[] arr, int target)
    {
        int start = 0;
        int end = arr.length-1;
        while(start+1 < end)
        {
            int mid = start+ (end-start)/2;
            if(target == arr[mid])
            {
                return mid;
            }else if (target > arr[mid])
            {
                start = mid;
            }else
            {
                end = mid;
            }  
        }
        if(arr[end] <= target) return end;
        if(arr[start] <= target) return start;
        return -1;
    }
}
```