C++ : Accepted: Binary Search
Gotchas\n- Given that array is sorted, the expectation is to use binary search to come with a optimum i.e better than O(n) time\n- Binary search needs to be mod
**Gotchas**\n- Given that array is sorted, the expectation is to use binary search to come with a optimum i.e better than O(n) time\n- Binary search needs to be modified as decribed below\n\n**Condition for binary search:**\n ```\n  // Case 1: x is closer to a[mid + k] than a[mid]\n  e.g \n  0 1 2 3 4 5 6 7\n [1,2,3,3,4,4,4,5] , x = 4, k = 3\n \n mid = 3, mid + k = 6 \n a[mid] = 3, a[mid + k] = 4\n \n x- a[mid] >  a[mid +k] - x\n4 - 3 > 4 - 0 \n// go right in this case which makes sense since output should be [4,4,4] which is on right side(LC verified with accepted soln)\n\n // Case 2:x is closer to a[mid] than a[mid+k]\n\n  e.g \n  0 1 2 3 4 5 6 7\n [1,2,3,3,4,4,4,5] , x = 2, k = 3\n \n mid = 3, mid + k = 6 \n a[mid] = 3, a[mid + k] = 4\n \n \nx- a[mid] <= a[mid + k] - x\n2 - 3 <= 4 - 2\n// go left in this case since expected output is [1,2,3](LC verified with accepted soln)\n```\nNote: absolute value does not work in following case so it is not used:\n```\ne.g \n     0 1 2 3 4 5 6 7 8 \nA = [1,1,2,2,2,2,2,3,3], x = 3, k = 2\nmid = 4, mid + k = 6\nA[mid] = 2 A[mid + k] =2\n\nx - A[mid ] > A[mid + k] - x\n3 - 2 > 2 - 3 // go right: correct\n\nabs(x - A[mid ]) =( x - A[mid + k] )\n1 == 1// go left: incorrect\n```\nModified version of example [here](https://leetcode.com/problems/find-k-closest-elements/discuss/106426/JavaC++Python-Binary-Search-O(log(N-K)-+-K)/437467)\n\n\n**Code:**\n```\nclass Solution {\npublic:\n    vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n     //modified  binary search   \n     int lo = 0;\n     // difference 1: note it is not arr.size()-1 ,i.e leave k elements\n     int hi = arr.size()-k -1;\n     while(lo <= hi)\n     {\n         int mid = lo+(hi-lo)/2;\n         \n         // difference 2: easy way to remember\n         // x is mid point :\n         // x = (arr[mid+k] + arr[mid +k])/2\n         // abs value will not work because sign is important to handle\n         \n         if(x - arr[mid] > arr[mid + k] -x)\n         {\n                // go right\n                lo = mid +1;\n         }\n         else\n         {\n             // difference 2: handle equals  and "less than" sign case with same logic \n             // go left\n             hi = mid-1;\n         }\n        }\n        \n        vector<int> res(arr.begin()+ lo, arr.begin()+ lo +k);\n        return res;\n    }\n};\n```\n\n**References/Credits:**\n- lee215\'s solution [here](https://leetcode.com/problems/find-k-closest-elements/discuss/106426/JavaC%2B%2BPython-Binary-Search-O(log(N-K)-%2B-K)), \n- ultrabendz\'s gotcha from lee215\'s  post [here](https://leetcode.com/problems/find-k-closest-elements/discuss/106426/JavaC++Python-Binary-Search-O(log(N-K)-+-K)/565500), \n- rosemelon\'s python implementation of  modified binary search from lee215\'s  post [here](https://leetcode.com/problems/find-k-closest-elements/discuss/106426/JavaC++Python-Binary-Search-O(log(N-K)-+-K)/282291). I have been using rose\'s implementation so far. Consequently, this post continues with the same implementation (i.e same bound values for lo and hi variables)\n\n**Intuition/Retention**\nThe solution was not intuitive to me. However, the posts above helped.\nI plan to remember this solution as a technique with following strategy:\n1. Gotcha 1: x is the mid pt of a[mid] and a[mid + k]\n2. take example with duplicate elements and reason out on whether to go left or right\n3. Gotcha 2:The end bound is not last element but last element - k
['C', 'Binary Tree']