Pencarian dalam Struktur Data: Metode Pencarian Berbeda Dijelaskan
Diterbitkan: 2021-05-03Jaringan komunikasi berkembang, dan orang-orang menggunakan internet! Bisnis akan digital untuk manajemen yang efisien. Data yang dihasilkan di internet meningkat, dan dengan demikian kumpulan data menjadi kompleks. Sangat penting untuk mengatur, mengelola, mengakses, dan menganalisis data dengan hati-hati dan efisien, struktur data adalah teknik yang paling membantu, dan artikel berfokus pada hal yang sama!
Daftar isi
Struktur data
Dalam ilmu komputer, struktur data adalah dasar untuk tipe data abstrak (ADT), di mana ADT adalah bentuk logis dari tipe data. Tata letak fisik tipe data diimplementasikan menggunakan struktur data. Tipe struktur data yang berbeda digunakan untuk berbagai jenis aplikasi; beberapa khusus dalam tugas-tugas tertentu.
Struktur data adalah kumpulan nilai data dan hubungan di antara mereka, operasi dan fungsi yang berlaku untuk data. Ini membantu dalam mengatur, mengelola dan menyimpan data dalam format tertentu. Dengan demikian, pengguna dapat memiliki akses mudah dan memodifikasi data secara efisien.
Struktur data membantu mengelola data dalam jumlah besar, seperti database besar. Algoritma yang efisien dibangun berdasarkan struktur data yang efisien. Selain penyimpanan yang efisien, struktur data juga bertanggung jawab atas pengambilan informasi yang efisien dari memori yang disimpan. Ini termasuk array, Linked List, Pointer, Searching, Stack, Graph, Queue, Structure, Programs, Sorting dan sebagainya.
Artikel ini mencakup konsep Pencarian dalam Struktur Data dan metodenya. Dua contoh algoritma dijelaskan secara rinci untuk memahami konsep dengan jelas. Untuk memperoleh pengetahuan, keterampilan, dan keahlian lebih lanjut, tersedia kursus online tentang struktur data, yang disebutkan di akhir artikel.
Apa itu Pencarian dalam Struktur Data?
Proses menemukan informasi yang diinginkan dari kumpulan item yang disimpan dalam bentuk elemen dalam memori komputer disebut sebagai 'pencarian dalam struktur data'. Kumpulan item ini dalam berbagai bentuk, seperti larik, pohon, grafik, atau daftar tertaut. Cara lain untuk mendefinisikan pencarian dalam struktur data adalah dengan menempatkan elemen karakteristik tertentu yang diinginkan dalam kumpulan item.
Metode Pencarian
Pencarian dalam struktur data dapat dilakukan dengan menerapkan algoritma pencarian untuk memeriksa atau mengambil elemen dari segala bentuk struktur data yang tersimpan. Algoritma ini dikategorikan berdasarkan jenis operasi pencariannya, seperti:
- Pencarian berurutan
Larik atau daftar elemen dilalui secara berurutan sambil memeriksa setiap komponen himpunan.
Misalnya, Pencarian Linier.
- Pencarian Interval
Algoritma yang dirancang secara eksplisit untuk pencarian dalam struktur data yang diurutkan termasuk dalam pencarian interval. Efisiensi algoritma ini jauh lebih baik daripada algoritma pencarian linier.
Misalnya, Pencarian Biner, Pencarian Logaritma.
Metode-metode ini diperiksa berdasarkan waktu yang dibutuhkan oleh suatu algoritma untuk mencari elemen yang cocok dengan item pencarian dalam kumpulan data dan diberikan oleh,
- Waktu sebaik mungkin
- Waktu rata-rata
- Waktu kasus terburuk
Kekhawatiran utama adalah mengenai waktu kasus terburuk yang mengarah pada prediksi yang dijamin dari kinerja algoritme dan juga mudah dihitung dibandingkan dengan waktu rata-rata.
Untuk mengilustrasikan contoh dan konsep dalam artikel ini, item 'n' dalam pengumpulan data dalam format data apa pun dipertimbangkan. Operasi dominan digunakan untuk menyederhanakan analisis dan perbandingan algoritma. Untuk pencarian dalam struktur data, perbandingan adalah operasi dominan, yang dilambangkan dengan O() dan diucapkan sebagai “Oh-besar” atau “Oh”.
Ada banyak algoritma pencarian dalam struktur data seperti pencarian linier, pencarian biner, pencarian interpolasi, pencarian melompat, pencarian eksponensial, pencarian Fibonacci, pencarian sublist, pencarian biner di mana-mana, pencarian biner tak terbatas, fungsi rekursif untuk pencarian substring, dan program rekursif. untuk mencari elemen secara linier dalam larik yang diberikan. Artikel ini dibatasi untuk algoritma pencarian linier dan biner dan prinsip kerjanya.
Mari dapatkan wawasan mendetail tentang pencarian linier dan pencarian biner dalam struktur data.
Pencarian Linier
Algoritma pencarian linier mencari semua elemen dalam array secara berurutan. Waktu eksekusi terbaiknya adalah satu, sedangkan waktu eksekusi terburuknya adalah n, di mana n adalah jumlah total item dalam larik pencarian.
Ini adalah algoritma pencarian paling sederhana dalam struktur data dan memeriksa setiap item dalam kumpulan elemen hingga cocok dengan elemen pencarian hingga akhir pengumpulan data. Ketika data tidak disortir, algoritma pencarian linier lebih disukai.
Pencarian linier memiliki beberapa kompleksitas seperti yang diberikan di bawah ini:
- Kompleksitas Ruang
Kompleksitas ruang untuk pencarian linier adalah O(n) karena tidak menggunakan ruang tambahan di mana n adalah jumlah elemen dalam array.
- Kompleksitas Waktu
*Kompleksitas kasus terbaik = O(1) terjadi ketika elemen pencarian ada pada elemen pertama dalam larik pencarian.
*Kompleksitas kasus terburuk = O(n) terjadi ketika elemen pencarian tidak ada dalam himpunan elemen atau larik.
*Kompleksitas rata-rata = O(n) dirujuk ketika elemen ada di suatu tempat dalam larik pencarian.
Contoh,
Mari kita ambil array elemen seperti yang diberikan di bawah ini:
45, 78, 12, 67, 08, 51, 39, 26
Untuk menemukan '51' dalam larik 8 elemen yang diberikan di atas, algoritma pencarian linier akan memeriksa setiap elemen secara berurutan hingga penunjuknya menunjuk ke 51 di ruang memori. Dibutuhkan O(6) waktu untuk menemukan 51 dalam sebuah array. Untuk mencari 12, pada larik di atas, dibutuhkan O(3), sedangkan untuk 26, dibutuhkan waktu O(8).
Pencarian Biner
Algoritma ini menemukan item tertentu dengan membandingkan item paling tengah dalam pengumpulan data. Ketika kecocokan terjadi, itu mengembalikan indeks item. Ketika item tengah lebih besar dari item, ia mencari item pusat dari sub-array kiri. Sebaliknya, jika item tengah lebih kecil dari item pencarian, item tersebut mengeksplorasi bagian tengah item di sub-array kanan. Itu terus mencari item sampai menemukannya atau sampai ukuran sub-array menjadi nol.
Pencarian biner membutuhkan urutan item yang diurutkan. Ini lebih cepat daripada algoritma pencarian linier. Ia bekerja pada prinsip membagi dan menaklukkan.
Kompleksitas run-time = O(log n)
Algoritma pencarian biner memiliki kompleksitas seperti yang diberikan di bawah ini:
- Kompleksitas kasus terburuk = O (n log n)
- Kompleksitas rata-rata = O (n log n)
- Kompleksitas kasus terbaik = O (1)
Contoh,
Mari kita ambil algoritma yang diurutkan dari 08 elemen:
08, 12, 26, 39, 45, 51, 67, 78
Untuk menemukan 51 dalam larik elemen di atas,
Algoritma akan membagi sebuah array menjadi dua array, 08, 12, 26, 39 dan 45, 51, 67, 78
Karena 51 lebih besar dari 39, ia akan mulai mencari elemen di sisi kanan array.
Ini selanjutnya akan membagi menjadi dua seperti 45, 51 dan 67, 78
Karena 51 lebih kecil dari 67, ia akan mulai mencari di sebelah kiri sub-array itu.
Subarray itu lagi dibagi menjadi dua sebagai 45 dan 51.
Karena 51 adalah nomor yang cocok dengan elemen pencarian, itu akan mengembalikan nomor indeks elemen tersebut dalam array.
Ini akan menyimpulkan bahwa elemen pencarian 51 terletak di posisi ke-6 dalam sebuah array.
Pencarian biner mengurangi waktu hingga setengahnya karena jumlah perbandingan berkurang secara signifikan daripada algoritma pencarian linier.
Baca: Jenis-Jenis Struktur Data di Python
Pencarian Interpolasi
Ini adalah varian yang ditingkatkan dari algoritma pencarian biner dan bekerja pada posisi penyelidikan elemen pencarian. Mirip dengan algoritma pencarian biner, ini bekerja secara efisien hanya pada pengumpulan data yang diurutkan.
Waktu eksekusi terburuk = O(n)
Ketika lokasi elemen target diketahui dalam pengumpulan data, pencarian interpolasi digunakan. Untuk menemukan nomor di direktori telepon, jika seseorang ingin mencari nomor telepon Monica, alih-alih menggunakan pencarian linier atau biner, seseorang dapat langsung menyelidiki penyimpanan ruang memori di mana nama dimulai dari 'M'.
Kesimpulan
Pencarian dalam struktur data mengacu pada menemukan elemen tertentu dalam larik elemen 'n'. Ada dua kategori, yaitu. Pencarian berurutan dan pencarian interval dalam pencarian. Hampir semua algoritma pencarian didasarkan pada salah satu dari dua kategori ini. Pencarian linier dan biner adalah dua algoritma sederhana dan mudah diimplementasikan di mana biner bekerja lebih cepat daripada algoritma linier.
Meskipun pencarian linier paling mudah, ia memeriksa setiap elemen sampai menemukan kecocokan dengan elemen pencarian, sehingga efisien ketika pengumpulan data tidak diurutkan dengan benar. Namun, jika pengumpulan data diurutkan dan panjang array cukup besar, maka pencarian biner lebih cepat.
Struktur data adalah bagian penting dari pemrograman komputer saat berurusan dengan kumpulan data. Pemrogram dan pengembang perlu terus memperbarui dan meningkatkan keterampilan mereka dengan dasar-dasar dan pembaruan dalam teknik pemrograman komputer. Pemrogram yang berurusan dengan struktur data harus sering memilih kursus.
Jika Anda penasaran untuk mempelajari lebih lanjut tentang ilmu data, lihat Program PG Eksekutif IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1-on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.
