Tugas Algoritma Pencarian XII IPA 1

Algoritma pencarian linier melakukan pencarian dengan cara:

• Membagi daftar menjadi dua bagian dan memeriksa elemen tengah.

• Memeriksa setiap elemen dalam daftar secara berurutan dari awal hingga akhir.

• Mengurutkan daftar terlebih dahulu sebelum melakukan pencarian.

• Menggunakan pohon biner untuk mempercepat pencarian.

• Membandingkan elemen pertama dan terakhir dalam daftar.

Kompleksitas waktu dari algoritma pencarian linier adalah:

• O(1)

• O(log n)

• O(n)

• O(n log n)

• O(n^2)

Algoritma pencarian biner hanya dapat digunakan pada daftar yang:

• Diurutkan terlebih dahulu

• Mengandung elemen unik

• Tidak mengandung elemen yang sama

• Sangat besar ukurannya

• Mengandung bilangan bulat saja

Keuntungan utama dari algoritma pencarian biner dibandingkan dengan pencarian linier adalah:

• Lebih mudah diimplementasikan

• Dapat digunakan pada daftar yang tidak diurutkan

• Lebih cepat untuk daftar yang besar dan diurutkan

• Tidak memerlukan langkah pengurutan sebelumnya

• Menghasilkan hasil yang lebih akurat

Dalam skenario di mana daftar data tidak diurutkan dan hanya akan digunakan satu kali, algoritma yang paling efisien untuk digunakan adalah:

• Pencarian biner karena lebih cepat

• Pencarian linier karena tidak memerlukan pengurutan

• Pencarian linier karena lebih akurat

• Pencarian biner karena kompleksitas waktu O(log n)

• Pencarian linier karena kompleksitas waktu O(n log n)

Jika Anda memiliki daftar berisi 1000 elemen yang diurutkan dan Anda menggunakan algoritma pencarian biner, berapa langkah maksimal yang diperlukan untuk menemukan elemen?

• 10

• 50

• 100

• 500

• 1000

Kelemahan dari algoritma pencarian linier dibandingkan dengan pencarian biner adalah:

• Memerlukan waktu pengurutan yang lebih lama

• Tidak dapat digunakan untuk daftar dengan elemen yang duplikat

• Lebih lambat pada daftar yang sangat besar

• Memerlukan lebih banyak ruang memori

• Hanya dapat digunakan pada data yang diurutkan

Dalam hal kompleksitas waktu, algoritma pencarian biner memiliki:

• O(n)

• O(log n)

• O(n log n)

• O(n^2)

• O(1)

Untuk daftar yang sangat kecil, keuntungan utama dari menggunakan algoritma pencarian linier adalah:

• Kompleksitas waktu yang lebih baik

• Lebih mudah diimplementasikan

• Tidak memerlukan pengurutan terlebih dahulu

• Lebih cepat dari pencarian biner

• Lebih akurat dalam menemukan elemen

Mengapa pencarian biner tidak dapat digunakan pada daftar yang tidak diurutkan?

• Karena pencarian biner hanya bekerja pada bilangan bulat

• Karena pencarian biner memerlukan data yang diurutkan untuk membagi daftar secara efektif

• Karena pencarian biner menggunakan pengurutan sebelum pencarian

• Karena pencarian biner hanya dapat digunakan pada data yang diurutkan dalam urutan menurun

• Karena pencarian biner membutuhkan lebih banyak ruang memori