[2 Minute Read] Binary Search and Two Pointer
The idea is to find the possible possition where x could be. This could be done using Binary Search in logarithmic time complexity as the array is sorted. \n\nL
The idea is to find the possible possition where ```x``` could be. This could be done using Binary Search in logarithmic time complexity as the array is sorted. \n\nLet\'s say that the number ```x``` was found at position ```i```. Then we would start with a window of size ```2 * k + 1```, i.e. in the window will be from ```[i - k, i + k]``` (with care for the array boundaries, i.e. if say, ```i - k < 0``` then the left boundary of our window would be ```0```, similarly for right boundary).\n\nNow we would start shrinking our window to a size of ```k``` by excluding the element from either side whose difference from x is greater. If the two boundary elements have same difference then we would remove the element from the right boundary (as mentioned in the question).\n\nSo the total time complexity becomes ```O(log n)``` for Binary Search and ```O(n)``` for Shrinking window size which gets amortized to a total time complexity of ```O(n)```.\n\nBelow is the Java code for above approach.\n\n```java\nclass Solution {\n    public List<Integer> findClosestElements(int[] arr, int k, int x) {\n        int n = arr.length;\n        // 1. Binary Search for possible possition\n        int l = 0, r = n - 1, pos = 0;\n        while(l <= r) {\n            int m = l + (r - l) / 2;\n            if(arr[m] <= x) {\n                pos = m;\n                l = m + 1;\n            }\n            else {\n                r = m - 1;\n            }\n        }\n        \n        // 2. Window from i - k to i + k\n        l = (pos - k < 0) ? 0 : pos - k;\n        r = (pos + k >= n) ? n - 1 : pos + k;\n        // 3. Shrink window to size k\n        while(r - l + 1 != k) {\n            if(Math.abs(arr[l] - x) > Math.abs(arr[r] - x)) {\n                l++;\n            }\n            else r--;\n        }\n        \n        // 4. Our answer is from l to r\n        List<Integer> ans = new ArrayList<>();\n        for(int i = l; i <= r; i++) {\n            ans.add(arr[i]);\n        }\n        return ans;\n    }\n}\n```
['Two Pointers', 'Binary Tree', 'Java']