Given an ordered integer list, return the largest integer less than N and smallest integer greater than N. If there is none for one, just print “X”.
Advertisement
Answer
As far as I know, this is the fastest solution possible.
def binary_search(arr, x): low = 0 high = len(arr) - 1 mid = 0 lm = -1 while low <= high: lm = mid mid = (high + low) // 2 if arr[mid] < x: low = mid + 1 elif arr[mid] > x: high = mid - 1 else: return mid if lm == mid:break return mid def find_next_bigger(arr,n,i): while i < len(arr): if arr[i] > n: return arr[i] i += 1 return arr[i] if i < len(arr) else "X" def find_next_smaller(arr, n,i): while i >= 0: if arr[i] < n: return arr[i] i -= 1 return arr[i] if i > 0 else "X" def solution(arr, n): if n > arr[-1]: return arr[-1], "X" if arr[0] > n: return "X", arr[0] i = binary_search(arr, n) bigger = find_next_bigger(arr, n, i) smaller = find_next_smaller(arr,n,i) return smaller, bigger