How to Find the Closest Number in a List: Min() vs. Bisection Method?

Finding the Closest Number in a List

Given a list of unsorted integers, determining the number closest to a given value is a common programming task. To achieve this, several approaches exist.

Using min() Function

If the list is not sorted, the min() function offers a quick and efficient solution. It considers each element in the list and returns the one with the minimum absolute difference from the provided number.

>>> myList = [4, 1, 88, 44, 3]
>>> myNumber = 5
>>> min(myList, key=lambda x:abs(x-myNumber))
4

Bisection Method

If the list is already sorted or can be sorted efficiently, the bisection method is a more effective approach. It takes O(log n) time, where n is the number of elements in the list.

def takeClosest(arr, target):
  left = 0
  right = len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
      return arr[mid]
    elif arr[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  if left == 0 or arr[left-1] > target:
    return arr[left]
  return arr[left-1]

The time complexity of the min() function approach is O(n), whereas the bisection method's time complexity is O(log n), providing a significant performance advantage for larger lists.

The above is the detailed content of How to Find the Closest Number in a List: Min() vs. Bisection Method?. For more information, please follow other related articles on the PHP Chinese website!