Wie finde ich die nächstgelegene Zahl in einer Liste: Min() vs. Halbierungsmethode?

Finden der nächsten Zahl in einer Liste

Bei einer gegebenen Liste unsortierter Ganzzahlen ist die Bestimmung der Zahl, die einem bestimmten Wert am nächsten kommt, eine gängige Programmierung Aufgabe. Um dies zu erreichen, gibt es mehrere Ansätze.

Verwendung der Funktion min()

Wenn die Liste nicht sortiert ist, bietet die Funktion min() eine schnelle und effiziente Lösung. Es berücksichtigt jedes Element in der Liste und gibt dasjenige mit der minimalen absoluten Differenz von der angegebenen Zahl zurück.

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

Halbierungsmethode

Wenn die Liste bereits sortiert ist oder effizient sortiert werden können, ist die Halbierungsmethode ein effektiverer Ansatz. Es dauert O(log n) Zeit, wobei n die Anzahl der Elemente in der Liste ist.

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]

Die Zeitkomplexität des min()-Funktionsansatzes beträgt O(n), während die Zeit der Halbierungsmethode die Zeit ist Die Komplexität beträgt O(log n), was einen erheblichen Leistungsvorteil für größere Listen bietet.

Das obige ist der detaillierte Inhalt vonWie finde ich die nächstgelegene Zahl in einer Liste: Min() vs. Halbierungsmethode?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!