How to Find the Closest Number in a List of Integers?

Finding the Closest Number to a Given Value in a List of Integers

Suppose we have a list of integers and want to determine which number is closest to a given value. We can employ various methods to achieve this.

Using min() Function for Unsorted Lists:

If we cannot guarantee that the list is sorted, we can leverage the built-in min() function. It selects the element with the minimum distance from the specified number using a key function.

>>> min(myList, key=lambda x:abs(x-myNumber))
4

This method efficiently finds the closest number in O(n) time complexity.

Using Bisection Method for Sorted Lists:

If the list is already sorted, or we are willing to sort it once, we can employ the bisection method. This method reduces the time complexity to O(log n). However, checking if the list is already sorted takes O(n), and sorting itself requires O(n log n).

>>> low, high = 0, len(myList) - 1
>>> while low <= high:
>>>     mid = (low + high) // 2
>>>     if myList[mid] == myNumber:
>>>         return myList[mid]
>>>     elif myList[mid] > myNumber:
>>>         high = mid - 1
>>>     else:
>>>         low = mid + 1
>>>     if low > high:
>>>         closest = myList[high] if abs(myList[high] - myNumber) < abs(myList[low] - myNumber) else myList[low]
>>>         return closest

By selecting the closest element, this method provides an optimal solution for sorted lists.

The above is the detailed content of How to Find the Closest Number in a List of Integers?. For more information, please follow other related articles on the PHP Chinese website!