[Java/C++/Python] Binary Search, O(log(N-K) + K)
Intuition\nThe array is sorted.\nIf we want find the one number closest to x,\nwe don\'t have to check one by one.\nit\'s straightforward to use binary research
# Intuition\nThe array is sorted.\nIf we want find the one number closest to `x`,\nwe don\'t have to check one by one.\nit\'s straightforward to use binary research.\n\nNow we want the `k` closest,\nthe logic should be similar.\n<br>\n\n# Explanation\nAssume we are taking `A[i] ~ A[i + k -1]`.\nWe can binary research `i`\nWe compare the distance between `x - A[mid]` and `A[mid + k] - x`\n\n\n@vincent_gui listed the following cases:\nAssume `A[mid] ~ A[mid + k]` is sliding window\n\ncase 1: x - A[mid] < A[mid + k] - x, need to move window go left\n-------x----A[mid]-----------------A[mid + k]----------\n\ncase 2: x - A[mid] < A[mid + k] - x, need to move window go left again\n-------A[mid]----x-----------------A[mid + k]----------\n\ncase 3: x - A[mid] > A[mid + k] - x, need to move window go right\n-------A[mid]------------------x---A[mid + k]----------\n\ncase 4: x - A[mid] > A[mid + k] - x, need to move window go right\n-------A[mid]---------------------A[mid + k]----x------\n\n\nIf `x - A[mid] > A[mid + k] - x`,\nit means `A[mid + 1] ~ A[mid + k]` is better than `A[mid] ~ A[mid + k - 1]`,\nand we have `mid` smaller than the right `i`.\nSo assign `left = mid + 1`.\n\n\n# Important\nNote that, you **SHOULD NOT** compare the **absolute value** of `abs(x - A[mid])` and `abs(A[mid + k] - x)`.\nIt fails at cases like `A = [1,1,2,2,2,2,2,3,3]`, `x = 3`, `k = 3`\n\nThe problem is interesting and good.\nUnfortunately the test cases is terrible.\nThe worst part of Leetcode test cases is that,\nyou submit a wrong solution but get accepted.\n\nYou didn\'t read my post and up-vote carefully,\nthen you miss this key point.\n<br>\n\n# Complexity\nTime `O(log(N - K))` to binary research and find result\nSpace `O(K)` to create the returned list.\n\n<br>\n\n**Java:**\n```java\n    public List<Integer> findClosestElements(int[] A, int k, int x) {\n        int left = 0, right = A.length - k;\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (x - A[mid] > A[mid + k] - x)\n                left = mid + 1;\n            else\n                right = mid;\n        }\n        return Arrays.stream(A, left, left + k).boxed().collect(Collectors.toList());\n    }\n```\n<br>\n\n**C++:**\n```cpp\n    vector<int> findClosestElements(vector<int>& A, int k, int x) {\n        int left = 0, right = A.size() - k;\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (x - A[mid] > A[mid + k] - x)\n                left = mid + 1;\n            else\n                right = mid;\n        }\n        return vector<int>(A.begin() + left, A.begin() + left + k);\n    }\n```\n\n<br>\n\n**Python:**\n```python\n    def findClosestElements(self, A, k, x):\n        left, right = 0, len(A) - k\n        while left < right:\n            mid = (left + right) / 2\n            if x - A[mid] > A[mid + k] - x:\n                left = mid + 1\n            else:\n                right = mid\n        return A[left:left + k]\n```
[]