Algoritma: Carian Linear dan Carian Binari

Terdapat beberapa algoritma ringkas yang memperkenalkan konsep asas logik dan struktur data, manakala yang lain bertujuan untuk kerumitan yang lebih besar.

Algoritma carian berguna untuk mencari maklumat dalam jumlah data, seperti mencari kenalan dalam buku telefon atau fail pada komputer.

Dalam pengertian ini, artikel ini bertujuan untuk membentangkan pengenalan kepada konsep yang melibatkan algoritma Carian Linear dan Carian Binari.

1. Carian Linear

• Imbas senarai secara berurutan untuk mencari elemen
• Contohnya ialah mencari nombor tertentu dalam tatasusunan

Algoritma Carian Linear, dalam pernyataan naratif, bermaksud mempunyai tatasusunan integer dan nilai yang akan menjadi rujukan untuk carian, dipanggil sasaran, yang akan menjadi parameter input. Dalam pengertian ini, terdapat fungsi yang menerima nilai ini, dan dengan itu, mula-mula ia melalui setiap kedudukan tatasusunan ini sehingga saiz maksimum kedudukan sedia ada, menggunakan terutamanya a untuk ini, dan kemudian, dengan jika, ia dikondisikan semakan untuk: sama ada setiap kedudukan mempunyai nilai yang sama dengan sasaran. Jika nilai ditemui, fungsi mengembalikan indeks kedudukan itu, atau mengembalikan -1, mewakili kes tidak ditemui.

Contoh menggunakan JavaScript ialah:

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

Oleh itu, algoritma ini bertujuan untuk mengembalikan kedudukan, atau indeks, di mana elemen itu berada, atau malah, ia hanya mencari elemen pertama yang sepadan, tanpa perlu meneruskan selepas menemuinya. Tingkah laku ini berlaku disebabkan oleh arahan algoritma, yang, apabila keadaannya dipenuhi, melaksanakan pulangan dengan indeks elemen, dan selepas itu ia keluar dari gelung, menamatkan fungsi.

Algoritma ini boleh berguna dalam senario yang terdapat senarai kecil atau tidak tersusun. Setiap elemen perlu dilalui dan tiada penggunaan memori tambahan.

2. Carian Binari

• Tatal senarai tersusun untuk mencari elemen
• Contohnya ialah mencari nombor tertentu dalam tatasusunan

Algoritma Carian Binari ialah bentuk algoritma yang lebih cekap untuk mencari nilai tertentu dalam tatasusunan yang diisih. Ini berfungsi dengan membahagikan julat carian berulang kali kepada separuh, yang menjadikannya lebih pantas daripada carian linear untuk set data yang besar. Carian binari mempunyai kerumitan O(log n), manakala carian linear ialah O(n).

Sebagai contoh dalam JavaScript, kami mempunyai:

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

Logiknya terdiri daripada bermula dengan dua penunjuk, satu di permulaan (rendah) dan satu lagi di hujung (tinggi) tatasusunan. Oleh itu, indeks tengah dikira const middle = Math.floor((rendah tinggi) / 2). Dengan ini, elemen tengah dibandingkan dengan sasaran pada setiap langkah: jika elemen tengah sama dengan sasaran, indeks dikembalikan. Walau bagaimanapun, jika elemen tengah lebih kecil daripada sasaran, atau tengah < sasaran, membayangkan membuang nombor terkecil, meletakkan permulaan sebagai rendah = tengah 1. Jika elemen tengah pula, lebih besar daripada sasaran tengah > sasaran, nombor yang lebih besar daripada sasaran dibuang, melaraskan indeks akhir kepada tinggi = tengah - 1. Proses ini diulang sehingga sasaran ditemui atau apabila julat menjadi tidak sah, dalam kes rendah > tinggi.

Carian binari boleh menjadi cekap apabila mencari data tersusun, seperti dalam kamus abjad atau set tarikh tersusun. Mereka cenderung untuk menjadi lebih pantas dan lebih cekap, kerana masalah itu boleh dibahagikan kepada submasalah yang lebih kecil dalam setiap lelaran.

Oleh itu, difahamkan bahawa carian linear adalah mudah dan berfungsi pada senarai kecil. Carian binari adalah lebih cekap, tetapi memerlukan data tersusun.

Memahami cara algoritma yang berbeza berfungsi dan konteks penggunaannya ialah langkah penting ke arah membina penyelesaian pengiraan yang cekap. Cuba laksanakan dan analisa kaedah ini, dan temui cara strategi ini boleh disesuaikan untuk menyelesaikan cabaran dunia sebenar. =)

Atas ialah kandungan terperinci Algoritma: Carian Linear dan Carian Binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!