Pencarian
Mencari dalam daftar
- Pencarian berarti menemukan apakah suatu nilai ada dalam daftar, dan di mana lokasinya.
- Jawaban yang umum adalah indeks dari nilai tersebut, atau
-1jika nilainya tidak ditemukan. - Dua metode klasik adalah pencarian linear dan pencarian biner.
Pencarian linear
- Periksa setiap item satu per satu, mulai dari awal.
- Berhenti segera setelah Anda menemukan kecocokan.
- Ini bekerja pada semua daftar, terurut atau tidak.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Pencarian biner
- Pencarian biner memerlukan daftar yang terurut.
- Lihat item di tengah. Jika itu adalah target, berhenti.
- Jika target lebih kecil, cari setengah kiri; jika lebih besar, cari setengah kanan.
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
Bandingkan keduanya
- Pencarian linear mungkin memeriksa setiap item — lambat untuk daftar yang panjang.
- Pencarian biner membuang setengah daftar setiap langkah, sehingga jauh lebih cepat.
- Namun pencarian biner hanya bekerja jika datanya sudah terurut.
Dalam pseudocode Cambridge
- Catatan:
DIVadalah pembagian bilangan bulat (Python menggunakan//). - Array di Cambridge biasanya berjalan dari 1 hingga
n, yaitu jumlah item.LENGTH()digunakan untuk string, sehingga perulangan menggunakann.
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
Kesalahan umum
- Pencarian biner memerlukan daftar yang terurut; ia memotong rentang menjadi setengah setiap langkah.
- Pencarian linear bekerja pada daftar apa pun tetapi lebih lambat.
Sekarang Anda coba
- Kembalikan indeks dari nilai tersebut, atau
-1ketika tidak ditemukan. - Tekan Periksa jawaban untuk menguji kode Anda.
Pencarian linear vs pencarian biner
Pencarian biner memotong setengah daftar setiap langkah — jauh lebih sedikit perbandingan.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis linear_search(items, target) untuk mencari indeks dari target di dalam items, atau kembalikan -1 jika tidak ditemukan. 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(items, target) untuk daftar terurut. Kembalikan indeks dari target, atau kembalikan -1 jika hilang. Bagilah jangkauan menjadi dua setiap langkah.
Klik Jalankan untuk melihat output di sini.
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis first_negative(items) yang memindai daftar dan mengembalikan indeks angka pertama yang kurang dari 0, atau kembalikan -1 jika tidak ada.
Klik Jalankan untuk melihat output di sini.