Find the closest number in a sorted list to a given target number 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 &gt;= arr[n - 1]):
        return arr[n - 1]
    # BSearch solution: Time &amp; Space: Log(N) 

    while (left &lt; right):
        mid = (left + right) // 2 # find the mid

        if (arr[mid] == target):
            return arr[mid]

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


Should be turned into:

if target &gt;= 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 &gt;= 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 &lt;= 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 &lt; right):
    mid = (left + right) // 2 # find the mid
    if arr[mid] == target:
        return arr[mid]

    if target &lt; 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 &lt; 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 &lt; or &gt;. This avoids making one extra check that will fail most of the times:

while left &lt; right:
    mid = (left + right) // 2  # find the mid
    if target &lt; arr[mid]:
        right = mid
    elif target &gt; 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 &gt;= 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 &gt;= arr[n - 1]:
        return arr[n - 1]
    # edge case - first or below all
    if target &lt;= arr[0]:
        return arr[0]
    # BSearch solution: Time &amp; Space: Log(N)

    while left &lt; right:
        mid = (left + right) // 2  # find the mid
        if target &lt; arr[mid]:
            right = mid
        elif target &gt; arr[mid]:
            left = mid + 1
        else:
            return arr[mid]

    if target &lt; 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 &gt;= val2 - target else val1