> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0658-find-k-closest-elements.md).

# 0658. Find K Closest Elements

<https://leetcode.com/problems/find-k-closest-elements>

## Description

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]
```

**Constraints:**

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

## ac

```java
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // edge cases

        // find x index
        int idx = findIndex(arr, x);

        // get k element
        List<Integer> res = new ArrayList<Integer>();
        int l = idx - 1, r = idx;
        if (arr[r] == x) {
            res.add(arr[r]);
            r++;
        }

        while (res.size() < k) {
            // take left
            if (r >= arr.length || l >= 0 && x - arr[l] <= arr[r] - x) {
                res.add(0, arr[l--]);
            } else { // take right
                res.add(arr[r++]);
            }
        }

        return res;
    }

    private int findIndex(int[] arr, int x) {
        int res = -1, l = 0, r = arr.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x) return mid;
            if (x < arr[mid]) r = mid;
            else l = mid;
        }

        // final check
        if (x <= arr[l]) return l;
        else if (x <= arr[r]) return r;
        else return r+1;
    }
}
/*
find index, compare left and right side, get smaller one
*/
```