class Solution:
  def searchMinDiffElement(self, arr, key):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if arr[mid] == key:
        return arr[mid]
      elif arr[mid] < key:
        lo = mid + 1
      else:
        hi = mid - 1
    
    # lo holds idx right after
    after = math.inf if lo >= len(arr) else arr[lo]
    # hi holds idx right before
    before = -math.inf if hi < 0 else arr[hi]
    
    if after - key < key - before:
      return after
    else:
      return before