# 658. Find K Closest Elements

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:**

<pre><code><strong>Input: arr = [1,2,3,4,5], k = 4, x = 3
</strong><strong>Output: [1,2,3,4]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: arr = [1,2,3,4,5], k = 4, x = -1
</strong><strong>Output: [1,2,3,4]
</strong></code></pre>

***My Solutions:***

用二分法找到x的位置。然后从x的左边第k个值、和x的右边第k个值作为一个window，通过比较左右边值谁更closer，把x的左右边值的window缩小，直到window的大小是k。

Time: O(logN)

```java
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int xIndex = findXIndex(arr, x);
        // x的左边和右边可能不够k个值
        int left = xIndex - k < 0 ? 0 : xIndex - k;
        int right = xIndex + k > arr.length - 1 ? arr.length - 1 : xIndex + k;
        while (left + k <= right) {
            if (Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) right--;
            else left++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = left; i <= right; i++) res.add(arr[i]);
        return res;
    }

    private int findXIndex(int[] arr, int x) {
        int l = 0, r = arr.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x) return mid;
            else if (arr[mid] < x) l = mid;
            else r = mid;
        }
        // if two adjacent values are same close, return the left one
        if (Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)) return l;
        else return r;
    }
}
```
