Algorithms: searching · Algoritma: pencarian
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
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.
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
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))
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
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.
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
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))
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
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.
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
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)
}
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
Kesalahan umum
- Pencarian biner memerlukan daftar yang terurut.
- Pencarian linear memeriksa setiap item secara bergantian.
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
Sekarang Anda coba
- Setiap tugas memberikan nama prosedur dan apa yang harus dikembalikannya.
- Tekan Periksa jawaban untuk menguji kode Anda.
Searching a list · Mencari dalam daftar
Binary search needs a sorted list but is far faster than linear. · Pencarian biner membutuhkan daftar yang terurut tetapi jauh lebih cepat daripada pencarian linear.
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one. · Tulis linear_search(lst, target). Kembalikan indeks dari target dalam lst, atau -1 jika tidak ada. Periksa item satu per satu.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1. · 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.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.