Python binary search with detailed explanation
Disclaimer - Although the solution is same others on leetcode, I am trying to explain it in a way that helped me understand it better. \n\nWe need to return k e
**Disclaimer** - *Although the solution is same others on leetcode, I am trying to explain it in a way that helped me understand it better. *\n\nWe need to return `k` elements that are closest to `x`. The input array is sorted in ascending order. So, we will try to find the starting point of these `k` elements i.e. the first element in this list of `k` elements which will make it easier to return the `k` elements. Let\'s call this first element of the output list `start`.\n\nObviously, `start` will lie between indices `0` and `length - k` where `length` is the length of the array. So, it makes sense to perform binary search on this section only. Therfore, we initialize `left=0` and `right = len(arr) - k`\n\nBecause we have to return `k` elements, it also makes sense to consider a window of `k` elements for comparison.\n\nConsider the following boundaries for the element `x`\n`left ......... mid ......... mid + k ......... right`\n\n1. `x <= arr[mid]` \n2. `arr[mid + k] <= x`\n3. `arr[mid] < x < arr[mid + k]`\n\n\n`Case 1 : x <= arr[mid]`\nIf `x` is less than `arr[mid]` then it\'s clear that `arr[mid + k`] cannot be a part of our output `k` elements. This is because there are `k + 1` elements between `arr[mid] and arr[mid + k]` inclusive. So, the `start` will either be `mid` or towards the left of it.\n\n`Case 2 : arr[mid + k] <= x`\nSimilar to previous case, `arr[mid]` cannot be a part of our output `k` elements because of the `k + 1` elements we have in between. Therefore, `start` will lie towards the right of `mid`\n\n`Case 3 : arr[mid] < x < arr[mid + k]`\nThis is more like a combination of the above two cases.\n\nA. If `x` is closer to `arr[mid]` then just like our case 1, `arr[mid + k]` cannot be a part of our output `k` elements. Therefore, our `start` will either be `mid` or towards the left of it. \n\nB. If `x` is closer to `arr[mid + k`], then just like case 2, `arr[mid]` cannot be a part of our output `k` elements, which means that our `start` will lie towards the right of `mid`.\n\nLet\'s implement this\n\n```\nclass Solution:\n    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n        left = 0\n        right = len(arr) - k\n        \n        while left < right:\n            mid = left + (right - left)//2\n\t\t\t\n            if x <= arr[mid]:\n                right = mid\n            elif x >= arr[mid + k]:\n                left = mid + 1\n            elif x - arr[mid] > arr[mid + k] - x:\n                left = mid + 1\n            else:\n                right = mid\n        return arr[left : left + k]\n```\n\nThe interesting part is that the first two `if-elif` conditions are handled by the last two conditionals. So, we can simply eliminate them. \n\n```\nclass Solution:\n    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n        left = 0\n        right = len(arr) - k\n        \n        while left < right:\n            mid = left + (right - left)//2\n\t\t\t\n            if x - arr[mid] > arr[mid + k] - x:\n                left = mid + 1\n            else:\n                right = mid\n        return arr[left : left + k]\n```\n\n\n\n
['Binary Tree']