Apakah algoritma carian untuk tatasusunan?

Himpunan algoritma carian tatasusunan: carian linear: melintasi tatasusunan, kerumitan masa O(n). Carian binari (tatasusunan tersusun sahaja): Bahagikan tatasusunan kepada dua, kerumitan masa O(log n). Jadual cincang: carian pantas menggunakan nilai kunci, kerumitan masa O(1).

Senarai komprehensif algoritma carian tatasusunan

Dalam sains komputer, algoritma carian tatasusunan digunakan untuk mencari elemen tertentu dalam tatasusunan tertib atau tidak tertib. Artikel ini akan meneroka pelbagai algoritma carian tatasusunan, termasuk kerumitan masa dan contoh praktikalnya.

Carian linear

Kerumitan masa: O(n)

Carian linear ialah algoritma carian paling mudah dan paling langsung. Ia bermula dari permulaan tatasusunan dan membandingkan elemen satu demi satu sehingga ia menjumpai elemen sasaran atau mencapai penghujung tatasusunan.

def linear_search(arr, target):
  for i in range(len(arr)):
    if arr[i] == target:
      return i
  return -1

Carian binari

Kerumitan masa: O(log n)

Carian binari digunakan untuk mencari dalam tatasusunan tersusun. Ia menyempitkan carian dengan berulang kali membahagikan tatasusunan kepada separuh.

def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1

Jadual cincang

Kerumitan masa: O(1)

Jadual cincang ialah struktur data yang membolehkan kami mencari elemen dengan cepat mengikut nilai kunci. Tatasusunan boleh digunakan sebagai struktur data asas untuk jadual cincang, di mana indeks digunakan sebagai kunci.

def hash_search(arr, target):
  hash_table = {}
  for i in range(len(arr)):
    hash_table[arr[i]] = i
  if target in hash_table:
    return hash_table[target]
  else:
    return -1

Contoh Praktikal

Pertimbangkan contoh carian tatasusunan berikut untuk mencari markah pelajar:

students = [
  {'name': 'John Doe', 'score': 85},
  {'name': 'Jane Doe', 'score': 90},
  {'name': 'Bill Smith', 'score': 75},
  {'name': 'Alice Johnson', 'score': 95}
]

Jika kita ingin mencari skor "Alice Johnson", kita boleh menggunakan carian linear:

for student in students:
  if student['name'] == 'Alice Johnson':
    print(student['score'])  # 输出：95

Sebagai alternatif, jika tatasusunan diisih dengan nama, kita boleh Gunakan carian binari:

students.sort(key=lambda x: x['name'])

left, right = 0, len(students) - 1
while left <= right:
  mid = (left + right) // 2
  if students[mid]['name'] == 'Alice Johnson':
    print(students[mid]['score'])  # 输出：95
    break
  elif students[mid]['name'] < 'Alice Johnson':
    left = mid + 1
  else:
    right = mid - 1

Atas ialah kandungan terperinci Apakah algoritma carian untuk tatasusunan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!