Taking @bipll suggestion you can restructure the while a bit. Considering you are only getting if arr[mid] == target at the very last iteration you can do it last and first check for < or >. This avoids making one extra check that will fail most of the times:
Taking @bipll suggestion you can restructure the while a bit. Considering you are only getting if arr[mid] == target at the very last iteration you can do it last and first check for < or >:
Taking @bipll suggestion you can restructure the while a bit. Considering you are only getting if arr[mid] == target at the very last iteration you can first check for < or >. This avoids making one extra check that will fail most of the times:
Taking @bipll suggestion you can restructure the while a bit. Considering you are only getting if arr[mid] == target at the very last iteration you can do it last and first check for < or >:
while left < right: mid = (left + right) // 2 # find the mid if target < arr[mid]: right = mid elif target > arr[mid]: left = mid + 1 else: return arr[mid] def get_closest_value(arr, target): n = len(arr) left = 0 right = n - 1 mid = 0 # edge case - last or above all if target >= arr[n - 1]: return arr[n - 1] # edge case - first or below all if target <= arr[0]: return arr[0] # BSearch solution: Time & Space: Log(N) while left < right: mid = (left + right) // 2 # find the mid if arr[mid]target ==< targetarr[mid]: returnright arr[mid] = mid ifelif target <> arr[mid]: rightleft = mid + 1 else: left = mid +return 1arr[mid] if target < arr[mid]: return find_closest(arr[mid - 1], arr[mid], target) else: return find_closest(arr[mid], arr[mid + 1], target) # findClosest # We find the closest by taking the difference # between the target and both values. It assumes # that val2 is greater than val1 and target lies # between these two. def find_closest(val1, val2, target): return val2 if target - val1 >= val2 - target else val1 def get_closest_value(arr, target): n = len(arr) left = 0 right = n - 1 mid = 0 # edge case - last or above all if target >= arr[n - 1]: return arr[n - 1] # edge case - first or below all if target <= arr[0]: return arr[0] # BSearch solution: Time & Space: Log(N) while left < right: mid = (left + right) // 2 # find the mid if arr[mid] == target: return arr[mid] if target < arr[mid]: right = mid else: left = mid + 1 if target < arr[mid]: return find_closest(arr[mid - 1], arr[mid], target) else: return find_closest(arr[mid], arr[mid + 1], target) # findClosest # We find the closest by taking the difference # between the target and both values. It assumes # that val2 is greater than val1 and target lies # between these two. def find_closest(val1, val2, target): return val2 if target - val1 >= val2 - target else val1 Taking @bipll suggestion you can restructure the while a bit. Considering you are only getting if arr[mid] == target at the very last iteration you can do it last and first check for < or >:
while left < right: mid = (left + right) // 2 # find the mid if target < arr[mid]: right = mid elif target > arr[mid]: left = mid + 1 else: return arr[mid] def get_closest_value(arr, target): n = len(arr) left = 0 right = n - 1 mid = 0 # edge case - last or above all if target >= arr[n - 1]: return arr[n - 1] # edge case - first or below all if target <= arr[0]: return arr[0] # BSearch solution: Time & Space: Log(N) while left < right: mid = (left + right) // 2 # find the mid if target < arr[mid]: right = mid elif target > arr[mid]: left = mid + 1 else: return arr[mid] if target < arr[mid]: return find_closest(arr[mid - 1], arr[mid], target) else: return find_closest(arr[mid], arr[mid + 1], target) # findClosest # We find the closest by taking the difference # between the target and both values. It assumes # that val2 is greater than val1 and target lies # between these two. def find_closest(val1, val2, target): return val2 if target - val1 >= val2 - target else val1 def get_closest_value(arr, target): n = len(arr) left = 0 right = n - 1 mid = 0 # edge case - last or above all if target >= arr[n - 1]: return arr[n - 1] # edge case - first or below all if target <= arr[0]: return arr[0] # BSearch solution: Time & Space: Log(N) while left < right: mid = (left + right) // 2 # find the mid if arr[mid] == target: return arr[mid] if target < arr[mid]: right = mid else: left = mid + 1 if target < arr[mid]: return find_closest(arr[mid - 1], arr[mid], target) else: return find_closest(arr[mid], arr[mid + 1], target) # findClosest # We find the closest by taking the difference # between the target and both values. It assumes # that val2 is greater than val1 and target lies # between these two. def find_closest(val1, val2, target): return val2 if target - val1 >= val2 - target else val1 # Sample code arr = [1, 2, 3, 4, 5, 5, 8, 10] target = 7 print(get_closest_value(arr, target)) # 8 def get_closest_value(arr, target): n = len(arr) left = 0 right = n - 1 mid = 0 # edge case - last or above all if target >= arr[n - 1]: return arr[n - 1] # edge case - first or below all if target <= arr[0]: return arr[0] # BSearch solution: Time & Space: Log(N) while left < right: mid = (left + right) // 2 # find the mid if arr[mid] == target: return arr[mid] if target < arr[mid]: right = mid else: left = mid + 1 if target < arr[mid]: return find_closest(arr[mid - 1], arr[mid], target) else: return find_closest(arr[mid], arr[mid + 1], target) # findClosest # We find the closest by taking the difference # between the target and both values. It assumes # that val2 is greater than val1 and target lies # between these two. def find_closest(val1, val2, target): return val2 if target - val1 >= val2 - target else val1 # Sample code arr = [1, 2, 3, 4, 5, 5, 8, 10] target = 7 print(get_closest_value(arr, target)) # 8 def get_closest_value(arr, target): n = len(arr) left = 0 right = n - 1 mid = 0 # edge case - last or above all if target >= arr[n - 1]: return arr[n - 1] # edge case - first or below all if target <= arr[0]: return arr[0] # BSearch solution: Time & Space: Log(N) while left < right: mid = (left + right) // 2 # find the mid if arr[mid] == target: return arr[mid] if target < arr[mid]: right = mid else: left = mid + 1 if target < arr[mid]: return find_closest(arr[mid - 1], arr[mid], target) else: return find_closest(arr[mid], arr[mid + 1], target) # findClosest # We find the closest by taking the difference # between the target and both values. It assumes # that val2 is greater than val1 and target lies # between these two. def find_closest(val1, val2, target): return val2 if target - val1 >= val2 - target else val1 lang-py