Comment trouver le nombre le plus proche dans une liste : méthode Min() ou méthode Bisection ?

Trouver le nombre le plus proche dans une liste

Étant donné une liste d'entiers non triés, déterminer le nombre le plus proche d'une valeur donnée est une programmation courante tâche. Pour y parvenir, plusieurs approches existent.

Utiliser la fonction min()

Si la liste n'est pas triée, la fonction min() propose une solution rapide et efficace. Il considère chaque élément de la liste et renvoie celui avec la différence absolue minimale par rapport au nombre fourni.

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

Méthode de bissection

Si la liste est déjà triée ou peuvent être triés efficacement, la méthode de bissection est une approche plus efficace. Cela prend un temps O(log n), où n est le nombre d'éléments dans la liste.

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]

La complexité temporelle de l'approche de la fonction min() est O(n), alors que le temps de la méthode de bissection la complexité est O (log n), offrant un avantage de performance significatif pour les listes plus grandes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!