Binary Search. Expected Position. C++. SubVector. Easy to understand.
The idea is to find the expected position of target in the array.\n\n\nif(element exists)\n\tget it\'s index\nelse\n\tget index just greater than x\n\n\nThen is
The idea is to find the expected position of target in the array.\n\n```\nif(element exists)\n\tget it\'s index\nelse\n\tget index just greater than x\n```\n\nThen isolate a range where we might find our answer.\n\n**Example**\nind: 0 1 2 3 4 5 6 {7} 8 9\n**arr: 0 0 1 2 3 3 4 {7} 7 8\nk = 3\nx = 5**\nExpected = Index 7 (5 should have been here)\n\nstart index = 7 - k = 7 - 3 = 4\nend index = 7 + k = 7 + 3 = 10 *(10 is out of range so take std::min(10,arr.size() - 1))*\n\nWe then close this range based on whose absolute value is less.\n\n```\nclass Solution {\npublic:\n    vector<int> subVector(vector<int> &arr, int start, int end) {\n        vector<int> result;\n\n        for (int i = start; i <= end; i++)\n            result.push_back(arr[i]);\n        return result;\n    }\n\n    vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n        int n = arr.size();\n        if (x < arr[0]) return subVector(arr, 0, k - 1);\n        if (arr[n - 1] < x) return subVector(arr, n - k, n - 1);\n\n        //Find Expected position of x\n        int left = 0;\n        int right = n - 1;\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n\n            if (arr[mid] < x) left = mid + 1;\n            else right = mid;\n        }\n        int expected = right;\n\n        //Get range\n        int si = std::max(0, expected - k);\n        int ei = std::min(expected + k, n - 1);\n\n        while (ei - si >= k) {\n            if (x - arr[si] <= arr[ei] - x) --ei;\n            else ++si;\n        }\n\n        return subVector(arr, si, ei);\n    }\n};\n```\n\n\u2728 STAR\uD83C\uDF1F if you found it useful.
['C', 'Binary Tree']