Searching
Daftar Isi
- Pendahuluan
- Algoritma Searching: Linear Search
- Algoritma Seaching: Binary Search
- Apakah Binary Search Lebih Efisien?
- Download Materi Power Point
- Referensi
Pendahuluan
Masalah seaching (pencarian) dalam sebuah list yang terurut.
- Diberikan sebuah daftar L yang berisi n elemen yang diurutkan dalam urutan tertentu (misalnya, numerik, abjad)
- Dan diberikan sebuah elemen tertentu x
- Tentukan apakah x muncul dalam list tersebut, dan jika ya, kembalikan indeks (posisi) x dalam list tersebut
Algoritma Searching: Linear Search
Algoritma Seaching: Binary Search
Ide dasarnya: Pada setiap langkah, lihat elemen tengah dari list yang tersisa untuk mengeliminasi separuhnya, dan dengan cepat mencapai elemen yang diinginkan.
Apakah Binary Search Lebih Efisien?
- Jumlah iterasi:
- Untuk daftar dengan n elemen, Binary Search paling banyak dapat dieksekusi sebanyak log2 n kali !!
- Linear Search, di sisi lain, dapat dieksekusi hingga n kali !!
- Jumlah komputasi per iterasi:
- Binary search melakukan lebih banyak komputasi daripada Linear Search per iterasi.
- Secara keseluruhan:
- Jika jumlah komponen kecil (misalnya, kurang dari 20), maka Linear Search lebih cepat.
- Jika jumlah komponen besar, maka Binary Search lebih cepat.
Download Materi Power Point
https://drive.google.com/drive/folders/1ATC6e-ocvKZ94CH_H5qjNdT9s6zimY_I?usp=drive_link
Referensi
-
