Bagaimana untuk Mencari Nombor Terhampir dalam Senarai: Min() vs. Kaedah Pembahagian?

Mencari Nombor Terhampir dalam Senarai

Memandangkan senarai integer tidak diisih, menentukan nombor yang paling hampir dengan nilai yang diberikan ialah pengaturcaraan biasa tugasan. Untuk mencapai matlamat ini, beberapa pendekatan wujud.

Menggunakan Fungsi min()

Jika senarai tidak diisih, fungsi min() menawarkan penyelesaian yang cepat dan cekap. Ia mengambil kira setiap elemen dalam senarai dan mengembalikan elemen yang mempunyai perbezaan mutlak minimum daripada nombor yang disediakan.

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

Kaedah Pembahagian

Jika senarai sudah diisih atau boleh diisih dengan cekap, kaedah belah dua adalah pendekatan yang lebih berkesan. Ia mengambil masa O(log n), dengan n ialah bilangan elemen dalam senarai.

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]

Kerumitan masa bagi pendekatan fungsi min() ialah O(n), manakala masa kaedah pembahagian dua kerumitan ialah O(log n), memberikan kelebihan prestasi yang ketara untuk senarai yang lebih besar.

Atas ialah kandungan terperinci Bagaimana untuk Mencari Nombor Terhampir dalam Senarai: Min() vs. Kaedah Pembahagian?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!