# [LeetCode 658. Find K Closest Elements ]()
### Daily challenge Jul 17, 2021 (EASY)

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

:::info
**Example 1:**
**Input:** arr = [1,2,3,4,5], k = 4, x = 3
**Output:** [1,2,3,4]
:::

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

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

---

### Approach 1 : Binary Search :bulb:
**`40 ms ( 65.40% )`** **`O()`**

利用 `Bianary Search` 找到 **`x`** 在 `arr` 中最靠近的位置 ( `x` 可能不存在 `arr` 中)。

找到後利用兩個 `pointer ( left & right )`，判斷何者較接近 `x`，並存入 `vector` 中，最後進行 `sort` 後回傳。

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int > ans;
        
        bool flag = false;
        int left = 0;
        int right = arr.size()-1;
        int middle = 0;
        
        // find index of value of x
        while(left <= right){
            cout << left << " " << right << endl;
            middle = (left + right) / 2;
            
            if(arr[middle] == x){
                flag = true;
                break;
            }
            else if(arr[middle] < x)    left = middle + 1;
            else    right = middle - 1;
        }
        
        // use two pointer to check which element is closer to x
        if(!flag){
            int t = left;
            left = right;
            right = t;
        }
        else{
            left = middle - 1;
            right = middle;
        }
        
        while(ans.size() != k){
            // when x is in the begin or end
            if(left < 0){
                for(int i=right; ans.size() != k; i++){
                    ans.push_back(arr[i]);
                }   
                break;
            }
            else if(right >=arr.size()){
                for(int i=left; ans.size() != k; i--){
                    ans.push_back(arr[i]);
                }
                break;
            }
            
            // between
            if( x - arr[left] <= arr[right] - x){
                ans.push_back(arr[left]);
                left--;
            }
            else{
                ans.push_back(arr[right]);
                right++;
            }
        }
        
        sort(ans.begin(), ans.end());
        return ans;
    }
};

### Approach 2 : Two Pointer :book:
**`36 ms ( 81.07% )`** **`O(N)`**

使用兩個 `pointer ( left & right )`，判斷 **`abs(arr[left] - x)、abs(arr[right] - x)`** 兩者的大小。

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size() - 1;
        
        while(right - left >= k){
            if(abs(arr[left] - x) > abs(arr[right] - x))    left++;
            else    right--;
        }
        
        return vector<int>(arr.begin() + left, arr.begin() + right + 1);
    }
};

### Approach 3 : Binary Search :book:
**`36 ms ( 81.07% )`** **`O(log(N - K))`**

:::danger
**`x - arr[mid]`** and **`arr[mid + k] - x`**，判斷時不能使用 abs()，結果會錯誤。
:::

>Assume we are taking **`A[left] ~ A[left + k -1]`**.
We can binary research `i`.
We compare the distance between `x - A[mid]` and `A[mid + k] - x`.
>
>* case 1: x - A[mid] < A[mid + k] - x, need to move window go `left`
-------**x**----A[mid]-----------------A[mid + k]----------
>* case 2: x - A[mid] < A[mid + k] - x, need to move window go `left`
-------A[mid]----**x**-----------------A[mid + k]----------
>* case 3: x - A[mid] > A[mid + k] - x, need to move window go `right`
-------A[mid]------------------**x**---A[mid + k]----------
>* case 4: x - A[mid] > A[mid + k] - x, need to move window go `right`
-------A[mid]---------------------A[mid + k]----**x**------
>
>`If x - A[mid] > A[mid + k] - x`,
it `means A[mid + 1] ~ A[mid + k]` is better than `A[mid] ~ A[mid + k - 1]`,
and we have mid `smaller` than the right `i`.
So assign `left = mid + 1`.

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0;
        int right = arr.size() - k;
        
        while(left < right){
            int middle = (left + right) / 2;
            
            if(x - arr[middle] > arr[middle + k] - x){
                left = middle + 1;
            }
            else{
                right = middle;
            }
        }
        
        return vector<int > (arr.begin() + left, arr.begin() + left + k);
    }
};