Algoritma: pencarian
Apa yang akan kita lakukan
- Algoritma adalah daftar langkah-langkah yang jelas yang memecahkan suatu masalah.
- Pekerjaan yang sangat umum adalah pencarian: mencari di mana nilai berada dalam sebuah daftar.
- Kita akan mempelajari dua algoritma: pencarian linear dan pencarian biner.
Pencarian linear
- Periksa item satu per satu, dari awal hingga akhir.
- Jika Anda menemukan nilainya, kembalikan indeks-nya (posisi).
- Jika Anda mencapai akhir dan tidak pernah menemukannya, kembalikan
-1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
Mengapa daftar terurut membantu
- Pencarian linear bekerja pada apa pun daftar, bahkan yang berantakan.
- Namun jika daftarnya terurut (kecil ke besar), kita bisa jauh lebih cepat.
- Pencarian biner menggunakan urutan terurut untuk melewatkan separuh daftar setiap kali.
Pencarian biner
- Lihat item di tengah.
- Jika itu adalah target, Anda selesai.
- Jika target lebih kecil, cari separuh kiri; jika lebih besar, separuh kanan. Ulangi.
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
Menggabungkan ide-ide
- Pencarian menggabungkan tiga blok pembangun yang sudah Anda ketahui.
- Sequencing: lakukan langkah-langkah secara berurutan. Selection:
if/elif/else. - Iteration: sebuah loop (
foratauwhile) mengulang pengecekan tersebut.
Dalam pseudocode AP CSP
- Ujian menulis loop dan pengecekan seperti ini.
FOR EACHmengunjungi setiap item;IFmemilih;REPEAT UNTILlooping hingga tes menjadi benar.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Kesalahan umum
- Pencarian biner memerlukan daftar yang terurut.
- Pencarian linear memeriksa setiap item secara bergantian.
Sekarang Anda coba
- Setiap tugas memberikan nama prosedur dan apa yang harus dikembalikannya.
- Tekan Periksa jawaban untuk menguji kode Anda.
Mencari dalam daftar
Pencarian biner membutuhkan daftar yang terurut tetapi jauh lebih cepat daripada pencarian linear.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis linear_search(lst, target). Kembalikan indeks dari target dalam lst, atau -1 jika tidak ada. Periksa item satu per satu.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis binary_search(sorted_lst, target) untuk daftar yang terurut kecil ke besar. Kembalikan indeks dari target, atau -1. Lihat tengah dan kurangi setengah area pencarian setiap kali.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis contains(lst, target) yang mengembalikan True jika target ada dalam lst, selain itu False. Anda dapat menggunakan kembali pencarian linear dan membandingkan hasilnya dengan -1.
Klik Jalankan untuk melihat output di sini.