cari
Rumahpembangunan bahagian belakangC++Apakah algoritma carian untuk tatasusunan?

Apakah algoritma carian untuk tatasusunan?

Jun 04, 2024 am 09:28 AM
tatasusunanalgoritma carian

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).

Apakah algoritma carian untuk tatasusunan?

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!

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Panjang umur c: memeriksa status semasaPanjang umur c: memeriksa status semasaApr 26, 2025 am 12:02 AM

C masih penting dalam pengaturcaraan moden kerana sifatnya yang cekap, fleksibel dan berkuasa. 1) C menyokong pengaturcaraan berorientasikan objek, sesuai untuk pengaturcaraan sistem, pembangunan permainan dan sistem tertanam. 2) Polimorfisme adalah kemuncak C, yang membolehkan panggilan untuk kaedah kelas yang diperoleh melalui penunjuk kelas asas atau rujukan untuk meningkatkan fleksibiliti dan skalabiliti kod.

C# vs Prestasi C: Penandaarasan dan PertimbanganC# vs Prestasi C: Penandaarasan dan PertimbanganApr 25, 2025 am 12:25 AM

Perbezaan prestasi antara C# dan C terutamanya dicerminkan dalam kelajuan pelaksanaan dan pengurusan sumber: 1) C biasanya melakukan lebih baik dalam pengiraan berangka dan operasi rentetan kerana ia lebih dekat dengan perkakasan dan tidak mempunyai overhead tambahan seperti pengumpulan sampah; 2) C# lebih ringkas dalam pengaturcaraan berbilang thread, tetapi prestasinya sedikit lebih rendah daripada C; 3) Bahasa yang harus dipilih harus ditentukan berdasarkan keperluan projek dan tumpukan teknologi pasukan.

C: Adakah ia mati atau hanya berkembang?C: Adakah ia mati atau hanya berkembang?Apr 24, 2025 am 12:13 AM

C isnotdying; it'sevolving.1) c suplemenvantduetoitsverversatilityandeficiencyinperformance-criticalapplications.2) thelanguageiscontinuouslyupdated, withc 20introducingfeatureslikemodulesandcoroutinestoMproveusability.3)

C Di Dunia Moden: Aplikasi dan IndustriC Di Dunia Moden: Aplikasi dan IndustriApr 23, 2025 am 12:10 AM

C digunakan secara meluas dan penting di dunia moden. 1) Dalam pembangunan permainan, C digunakan secara meluas untuk prestasi tinggi dan polimorfisme, seperti Unrealengine dan Perpaduan. 2) Dalam sistem perdagangan kewangan, latensi rendah C dan throughput yang tinggi menjadikannya pilihan pertama, sesuai untuk perdagangan frekuensi tinggi dan analisis data masa nyata.

C XML Perpustakaan: Membandingkan dan Berbeza PilihanC XML Perpustakaan: Membandingkan dan Berbeza PilihanApr 22, 2025 am 12:05 AM

Terdapat empat perpustakaan XML yang biasa digunakan di C: TinyXML-2, PugixML, Xerces-C, dan RapidXML. 1.TinyXML-2 sesuai untuk persekitaran dengan sumber terhad, fungsi ringan tetapi terhad. 2. PugixML cepat dan menyokong pertanyaan XPath, sesuai untuk struktur XML yang kompleks. 3.xerces-C berkuasa, menyokong resolusi DOM dan SAX, dan sesuai untuk pemprosesan kompleks. 4. RapidXML memberi tumpuan kepada prestasi dan parses sangat cepat, tetapi tidak menyokong pertanyaan XPath.

C dan XML: Meneroka hubungan dan sokonganC dan XML: Meneroka hubungan dan sokonganApr 21, 2025 am 12:02 AM

C Berinteraksi dengan XML melalui perpustakaan pihak ketiga (seperti TinyXML, PugixML, Xerces-C). 1) Gunakan perpustakaan untuk menghuraikan fail XML dan menukarnya ke dalam struktur data C-diproses. 2) Apabila menjana XML, tukar struktur data C ke format XML. 3) Dalam aplikasi praktikal, XML sering digunakan untuk fail konfigurasi dan pertukaran data untuk meningkatkan kecekapan pembangunan.

C# vs C: Memahami perbezaan dan persamaan utamaC# vs C: Memahami perbezaan dan persamaan utamaApr 20, 2025 am 12:03 AM

Perbezaan utama antara C# dan C ialah sintaks, prestasi dan senario aplikasi. 1) Sintaks C# lebih ringkas, menyokong pengumpulan sampah, dan sesuai untuk pembangunan rangka kerja .NET. 2) C mempunyai prestasi yang lebih tinggi dan memerlukan pengurusan memori manual, yang sering digunakan dalam pengaturcaraan sistem dan pembangunan permainan.

C# vs C: Sejarah, evolusi, dan prospek masa depanC# vs C: Sejarah, evolusi, dan prospek masa depanApr 19, 2025 am 12:07 AM

Sejarah dan evolusi C# dan C adalah unik, dan prospek masa depan juga berbeza. 1.C dicipta oleh BjarnestroustRup pada tahun 1983 untuk memperkenalkan pengaturcaraan berorientasikan objek ke dalam bahasa C. Proses evolusinya termasuk pelbagai standardisasi, seperti C 11 memperkenalkan kata kunci auto dan ekspresi Lambda, C 20 memperkenalkan konsep dan coroutin, dan akan memberi tumpuan kepada pengaturcaraan prestasi dan sistem pada masa akan datang. 2.C# telah dikeluarkan oleh Microsoft pada tahun 2000. Menggabungkan kelebihan C dan Java, evolusinya memberi tumpuan kepada kesederhanaan dan produktiviti. Sebagai contoh, C#2.0 memperkenalkan generik dan C#5.0 memperkenalkan pengaturcaraan tak segerak, yang akan memberi tumpuan kepada produktiviti pemaju dan pengkomputeran awan pada masa akan datang.

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

VSCode Windows 64-bit Muat Turun

VSCode Windows 64-bit Muat Turun

Editor IDE percuma dan berkuasa yang dilancarkan oleh Microsoft

Muat turun versi mac editor Atom

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Persekitaran pembangunan bersepadu PHP yang berkuasa

MinGW - GNU Minimalis untuk Windows

MinGW - GNU Minimalis untuk Windows

Projek ini dalam proses untuk dipindahkan ke osdn.net/projects/mingw, anda boleh terus mengikuti kami di sana. MinGW: Port Windows asli bagi GNU Compiler Collection (GCC), perpustakaan import yang boleh diedarkan secara bebas dan fail pengepala untuk membina aplikasi Windows asli termasuk sambungan kepada masa jalan MSVC untuk menyokong fungsi C99. Semua perisian MinGW boleh dijalankan pada platform Windows 64-bit.

DVWA

DVWA

Damn Vulnerable Web App (DVWA) ialah aplikasi web PHP/MySQL yang sangat terdedah. Matlamat utamanya adalah untuk menjadi bantuan bagi profesional keselamatan untuk menguji kemahiran dan alatan mereka dalam persekitaran undang-undang, untuk membantu pembangun web lebih memahami proses mengamankan aplikasi web, dan untuk membantu guru/pelajar mengajar/belajar dalam persekitaran bilik darjah Aplikasi web keselamatan. Matlamat DVWA adalah untuk mempraktikkan beberapa kelemahan web yang paling biasa melalui antara muka yang mudah dan mudah, dengan pelbagai tahap kesukaran. Sila ambil perhatian bahawa perisian ini