trjhtr

Given a list of n integers sorted in ascending order, find the closest
number (value) in the list to a given target number. How quickly can
you do it?

I'm interested to know if there's any feedback for my code.

def getClosestValue(arr, target):
 n = len(arr)
 left = 0
 right = n - 1
 mid = 0

 # edge case
 if (target >= arr[n - 1]):
 return arr[n - 1]
 # 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]):
 # If target is greater than previous
 # to mid, return closest of two
 if (mid > 0 and target > arr[mid - 1]):
 return findClosest(arr[mid - 1], arr[mid], target)
 # update right
 right = mid
 else:
 if (mid < n - 1 and target < arr[mid + 1]):
 return findClosest(arr[mid], arr[mid + 1], target)
 # update i
 left = mid + 1
 return arr[mid]

# 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 findClosest(val1, val2, target):
 if (target - val1 >= val2 - target):
 return val2
 else:
 return val1


# Sample code
arr = [1, 2, 3, 4, 5, 5, 8, 10]
target = 7
print(getClosestValue(arr, target))

Conventions

The Style guide to follow in Python is PEP8. If you do so, your code blends right into the python community and it is immediately easier to follow. On that regard you'll see that the functions name's don't follow the recommended style.

getClosestValue

Should actually be:

get_closest_value

The relevant quote from PEP8 for this case

Use the function naming rules: lowercase with words separated by
underscores as necessary to improve readability.

Still in this topic, all the parenthesis used in the ifs are redundant and break the style.

if (target >= arr[n - 1]):

Should be turned into:

if target >= arr[n - 1]:

Although i suspect that this may be a habit brought from other languages.

Edge cases

You contemplated the case where the value is the highest or above, which gives you a quick way out:

# edge case
if (target >= arr[n - 1]):
 return arr[n - 1]

However there is no corresponding edge case for when the value is the lowest or below. I believe you merely forgot it.

#edge case - first or below all
if target <= arr[0]:
 return arr[0]

Logic

Now both edge cases are covered, so the while can be simplified to only have the navigation to the corresponding item if there is one.

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

After this last while if there isn't an exact match, calculate the nearest to the one you ended on, and return it:

if target < arr[mid]:
 return find_closest(arr[mid - 1], arr[mid], target)
else:
 return find_closest(arr[mid], arr[mid + 1], target)

Note that i don't need to check if mid - 1 or mid + 1 is a valid index, because if it wasn't it would mean that the value was below or above all elements, and those cases were already covered in the beginning of the function.
This is not only simpler but also more efficient since it only checks for the closest on the very end and not at each iteration.

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:

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]

When i have a simple condition with a return on both cases i rather write them inline since its easy to read and a bit more concise:

def find_closest(val1, val2, target):
 return val2 if target - val1 >= val2 - target else val1

But don't go over the top on this. It can easily be harder to read depending on the complexity of the condition.

Full Modified Version

For you to get a better picture of all the changes i mentioned, i'll leave you with the full modified version:

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

python has a binary search implementation: https://docs.python.org/2/library/bisect.html

so just:

import bisect
ind = bisect.bisect_left(arr, target)

if you get ind > len(arr)-2, then the solution is arr[-1]. Otherwise you just hceck arr[ind] and arr[ind+1] to find whichever is closest

Strictly speaking, if you implemented your own binary search it should be just as fast. However, having a two line implementation is easier to read than defining your own functions