如何查找列表中最接近的数字：Min() 与二分法？

查找列表中最接近的数字

给定一个未排序整数列表，确定最接近给定值的数字是一种常见的编程任务。为了实现这一点，存在多种方法。

使用 min() 函数

如果列表未排序，min() 函数提供了快速高效的解决方案。它考虑列表中的每个元素，并返回与提供的数字的绝对差值最小的元素。

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

二分法

如果列表已排序或者可以有效排序，二分法是一种更有效的方法。需要 O(log n) 时间，其中 n 是列表中元素的数量。

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]

min() 函数方法的时间复杂度为 O(n)，而二分法的时间复杂度复杂度为 O(log n)，为较大的列表提供了显着的性能优势。

以上是如何查找列表中最接近的数字：Min() 与二分法？的详细内容。更多信息请关注PHP中文网其他相关文章！