Solution: Find the Closest Number

This review discusses the solution of the "find the closest number challenge" in detail.

Solution: 1

A simple and straight-forward solution to this problem would be to compute the absolute difference of the target from each list element iteratively, while keeping track of the minimum difference encountered so far.

def find_closest(lst, target):
"""
Finds the closest number to the target in the list
:param lst: Sorted list of integers
:param target: Left sided index of the list
:return: Closest element from the list to the target
"""
closest = abs(lst[0] - target) # Closest absolute difference
index = 0 # List index number
for i in range(len(lst)): # Traversing the whole list
if abs(lst[i] - (target)) <= closest: # Is there any number more closest?
closest = abs(lst[i] - (target)) # Saving the new closest number
index = i # Saving the index of the list
return lst[index] # Returning the result
# Driver code to test above function
if __name__ == '__main__':
print(find_closest([-9, -4, -2, 0, 1, 3, 4, 10], 5))
print(find_closest([1, 2, 5, 10, 23, 25, 30, 50], 100))

Explanation

  • Line 9-10: Initially saved the first index of the list and its index as the closest number
  • Line 13-15: While traversing the whole list, we are storing the more closest number and its index to the target
  • Line 17: Returning the closest element from the list

Time complexity

Since we have to go through each element one by one and compute its absolute difference, this solution is an O(n)O(n) ...

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.