# 658    Find K Closest Elements

## 658. [Find K Closest Elements](https://leetcode.com/problems/find-k-closest-elements/description/)

## 1. Question

Given a sorted array, two integers`k`and`x`, find the`k`closest elements to`x`in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

**Example 1:**

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

Output: [1,2,3,4]
```

**Example 2:**

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

Output: [1,2,3,4]
```

**Note:**

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10^4
3. Absolute value of elements in the array and x will not exceed 10^4

## 2. Implementation

**(1) Binary Search + Two Pointers**

思路: 这道题非常多corner cases要注意考虑

```java
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();

        if (arr == null || arr.length == 0) {
            return res;
        }

        int n = arr.length;

        if (x <= arr[0]) {
            return getSubArray(res, arr, 0, k - 1);
        }
        else if (x >= arr[n - 1]) {
            return getSubArray(res, arr, n - k, n - 1);
        }
        else {
            int index = binarySearch(arr, x);
            int low = Math.max(0, index - k);
            int high = Math.min(n - 1, index + k);

            while (high - low + 1 > k) {
                if (low < 0 || ((x - arr[low]) <= (arr[high] - x))) {
                    --high;
                }
                else if (high >= n || ((arr[high] - x) < (x - arr[low]))) {
                    ++low;
                }
                else {
                    break;
                }
            }
            return getSubArray(res, arr, low, high);
        }
    }

    public List<Integer> getSubArray(List<Integer> res, int[] arr, int start, int end) {
        for (int i = start; i <= end; i++) {
            res.add(arr[i]);
        }
        return res;
    }

    public int binarySearch(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (nums[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return nums[start] >= target ? start : end;
    }
}
```

## 3. Time & Space Complexity

**Binary Search + Two Pointers:** 时间复杂度O(logn + k), 空间复杂度O(k)