Comment trouver le nombre le plus proche dans une liste d'entiers ?

Trouver le nombre le plus proche d'une valeur donnée dans une liste d'entiers

Supposons que nous ayons une liste d'entiers et que nous voulions déterminer quel nombre est la plus proche d’une valeur donnée. Nous pouvons utiliser différentes méthodes pour y parvenir.

Utilisation de la fonction min() pour les listes non triées :

Si nous ne pouvons pas garantir que la liste est triée, nous pouvons tirer parti de la Fonction min() intégrée. Il sélectionne l'élément avec la distance minimale du nombre spécifié à l'aide d'une fonction clé.

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

Cette méthode trouve efficacement le nombre le plus proche dans la complexité temporelle O(n).

Utilisation de la méthode de bissection pour les listes triées :

Si la liste est déjà triée, ou si nous sommes prêts à la trier une fois, nous pouvons utiliser la bissection méthode. Cette méthode réduit la complexité temporelle à O(log n). Cependant, vérifier si la liste est déjà triée prend O(n), et le tri lui-même nécessite 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

En sélectionnant l'élément le plus proche, cette méthode fournit une solution optimale pour les listes triées .

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!