Pengantar Algoritma Pencarian Linear: Pengenalan & Fitur[Dengan Contoh]

Apa itu Pencarian?

Pencarian adalah proses menemukan elemen tertentu dalam daftar elemen. Ini membantu dalam mencari catatan tertentu. Oleh karena itu, ini adalah teknik mengidentifikasi tempat item tertentu. Keberhasilan suatu proses pencarian tergantung pada apakah item yang akan dicari telah teridentifikasi atau belum.

Struktur Data memungkinkan pencarian data melalui dua metode.

1. Pencarian linier atau pencarian berurutan
2. Pencarian biner

Pencarian Linier

Algoritma pencarian linier adalah jenis algoritma untuk pencarian sekuensial data. Algoritma ini menemukan elemen tertentu dengan kompleksitas O(n). Ini diterapkan pada koleksi item. Setiap item data dicari secara berurutan, dan dikembalikan jika cocok dengan elemen yang dicari. Jika tidak ditemukan kecocokan, maka pencarian terus berlanjut hingga akhir data yang terkumpul. Ini pada dasarnya adalah teknik menjelajahi setiap elemen saat melintasi daftar. Algoritma pencarian dapat diterapkan pada data yang diurutkan dan tidak disortir. Pencarian linier praktis jarang digunakan karena opsi pencarian yang lebih cepat disediakan oleh algoritma pencarian lain seperti algoritma pencarian biner dan tabel hash.

Langkah-langkah dalam algoritma pencarian linier

• Pembacaan elemen pencarian oleh pengguna.
• Elemen yang akan dicari dikompresi dengan elemen pertama dari daftar.
• Jika elemen cocok, maka pengembalian dihasilkan.
• Jika elemen tidak cocok maka elemen yang akan dicari dibandingkan dengan elemen kedua dari daftar.
• Proses ini diulang sampai elemen cocok.

Fitur algoritma pencarian linier

1. Ini biasanya diterapkan pada daftar kecil data yang tidak disortir atau tidak diurutkan.
2. Waktu bergantung secara linier pada jumlah elemen, oleh karena itu memiliki kompleksitas waktu jika O(n).
3. Implementasinya sangat sederhana.

Algoritma pencarian linier

Metode pengulangan terus menerus berlangsung kecuali dan sampai item ditemukan

• algoritma Seqnl_Search(daftar, item)
• Pra: daftar != ;
• Posting: kembalikan indeks item jika ditemukan, jika tidak: 1
• indeks <- fi
• while index < list.Cnt dan list[index] != item //cnt: variabel counter
• indeks <- indeks + 1
• akhiri sementara
• if index < list.Cnt dan list[index] = item
• indeks kembali
• berakhir jika
• kembali: 1
• akhiri Seqnl_Search

Contoh pencarian linier

Masalah: Diberikan sebuah array arr[] dari n elemen, tulis sebuah fungsi untuk mencari elemen x yang diberikan dalam arr[].

Gambar 1: Contoh kode yang menunjukkan implementasi algoritma pencarian linier

Sumber

Algoritma pencarian linier dapat digunakan dalam beberapa bahasa pemrograman.

1. Pencarian linier dengan Python

Gambar 2: Contoh kode yang menunjukkan algoritma pencarian linier dalam bahasa Python

Sumber

Output: Elemen hadir pada indeks 3

2. Pencarian linier di C

Gambar 3: Contoh kode yang menunjukkan algoritma pencarian linier dalam bahasa C

Sumber

Output : Elemen hadir pada indeks 3

3. Pencarian linier dalam struktur data

Pseudocode untuk masalah pencarian linier dalam struktur data adalah

Gambar 4: Pseudocode untuk algoritma pencarian linier

Sumber

Pencarian Biner

Pencarian biner adalah algoritma untuk mencari elemen dalam array elemen. Dibandingkan dengan algoritma pencarian linier, algoritma pencarian biner diterapkan pada daftar data yang diurutkan.

Algoritma pencarian biner mencakup langkah-langkah berikut:

• Perbandingan elemen yang akan dicari dengan elemen dari tengah daftar atau larik.
• Jika elemen cocok dengan elemen dari daftar, ia mengembalikan indeks elemen tengah.
• Jika tidak ada kecocokan yang dikembalikan, akan diperiksa apakah elemen lebih besar atau lebih kecil dari elemen di tengah.
• Untuk elemen dengan nilai lebih besar dari elemen tengah, pencarian dilakukan di sisi kanan array.
• Demikian pula, jika nilai elemen lebih rendah dari elemen tengah, maka pencarian dilakukan di sisi kiri daftar.

Oleh karena itu, pencarian biner paling baik diterapkan ketika data berisi elemen batang bilangan besar dengan cara yang diurutkan. Ini membuatnya menjadi syarat untuk algoritma pencarian bahwa daftar/array harus diurutkan.

Fitur Pencarian Biner

• Algoritma pencarian biner berguna untuk mencari sejumlah besar elemen dalam array.
• Algoritma pencarian biner memiliki kompleksitas waktu O(logn).
• Implementasi algoritma pencarian biner sederhana.

Algoritma Pencarian Biner

• Algoritma Binary_Search(daftar, item)
• Atur L ke 0 dan R ke n: 1
• jika L > R, maka Binary_Search berakhir sebagai tidak berhasil
• lain
• Atur m (posisi di elemen tengah) ke lantai (L + R) / 2
• jika Am < T, atur L ke m + 1 dan lanjutkan ke langkah 3
• jika Am > T, atur R ke m: 1 dan lanjutkan ke langkah 3
• Sekarang, Am = T,
• pencarian dilakukan; kembali (m)

Kesimpulan

Pada artikel ini, kita telah melihat apa itu Algoritma Pencarian Linier dan juga mempelajari secara detail bagaimana mencari elemen tertentu dari daftar menggunakan Algoritma Pencarian Linier. Terakhir, kami juga melihat bagaimana kami dapat menerapkan Algoritma Pencarian Linear secara praktis menggunakan Python 3 sebagai bahasa dan mendapatkan hasil yang kami inginkan.

Jika Anda tertarik dengan Ilmu Data, Anda harus memeriksa Program PG Eksekutif IIIT-B dan upGrad dalam Ilmu Data yang telah dibuat dengan cermat untuk para profesional yang bekerja dan menawarkan banyak studi kasus, lokakarya langsung, bimbingan 1-on-1, dan lebih banyak.