Python Binary Search w/ Clear Detailed Explanation
Please upvote if you found it helpful =) \nThank you!\n\n\tclass Solution:\n\t\tdef findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n\n\
Please upvote if you found it helpful =) \nThank you!\n\n\tclass Solution:\n\t\tdef findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:\n\n\t\t\t# if the length of the array is the same as k, we can\n\t\t\t# just return the array itself\n\t\t\tif len(arr) == k:\n\t\t\t\treturn arr\n\n\t\t\t# In this example, we are doing a modified binary search, instead of\n\t\t\t# looking for a particular value, we are looking for a range of a window.\n\n\t\t\t# we cannot do a regular binary search here because the sliding window\n\t\t\t# will out of index when it slides to the last k elements at the end of\n\t\t\t# the array. Thus, right pointer + k <= len(arr), so right = len(arr) - k\n\t\t\tleft, right = 0, len(arr) - k\n\n\t\t\t# When the left and the right pointer at the same position, we\'ve\n\t\t\t# searched through all possible elements in arr\n\t\t\twhile left < right:\n\n\t\t\t\t# set midpoint, in this case, the midpoint is the starting point of\n\t\t\t\t# the sliding window\n\t\t\t\tm = (left + right) // 2\n\n\t\t\t\t# since midpoint is the starting point of the sliding window, thus\n\t\t\t\t# the end point of the sliding window is m + k, because we are looking\n\t\t\t\t# for k elements.\n\t\t\t\t# use x - arr[m] to determine if the number at midpoint is greater\n\t\t\t\t# than the number at m + k, which is the end point of the window,\n\t\t\t\t# notice that we assume the midpoint < x here. If x - arr[m] is greater,\n\t\t\t\t# which means the number on the left side starts from midpoint is further\n\t\t\t\t# than the endpoint of the window, we may set left = mid + 1 to continue\n\t\t\t\t# searching from the right side\n\t\t\t\tif x - arr[mid] > arr[mid + k] - x:\n\t\t\t\t\tleft = mid + 1\n\n\t\t\t\t# Otherwise, when If x - arr[m] is smaller or equal to the endpoint, \n\t\t\t\t# of the window, which means the number on the\n\t\t\t\t# right side starts at the window endpoint is further than the \n\t\t\t\t# starting point of the window, we may set right = mid to continue\n\t\t\t\t# searching to the left side\n\t\t\t\telse:\n\t\t\t\t\tright = mid\n\t\t\t# After searching through all possible elements, return the sliding window\n\t\t\t# itself, we use start point as left to left + k to return k elements only\n\t\t\treturn arr[left : left + k]
['Binary Tree', 'Python']