Memeriksa Satu Per Satu
Pencarian Linear: Periksa Satu Per Satu
Bayangkan Anda memiliki 10 kartu menghadap ke bawah, bernomor 1 hingga 10, dikocok dalam urutan acak.
Anda ingin menemukan kartu dengan nomor 7.
Anda membalik kartu satu per satu, dari kiri ke kanan, sampai Anda menemukannya.
| Skenario | Flip diperlukan |
|---|---|
| Kasus terbaik | 1 flip (beruntung percobaan pertama!) |
| Kasus terburuk | 10 flip (itu kartu terakhir) |
| Rata-rata | sekitar 5 flip |
Sekarang bayangkan 100 kartu. Rata-rata: sekitar 50 flip.
1.000 kartu? Rata-rata: sekitar 500 flip.
Lihat polanya? Kartu berlipat ganda, pekerjaan berlipat ganda. Pekerjaan tumbuh dalam garis lurus.
Para ilmuwan komputer menyebutnya pencarian linear — linear berarti pekerjaan tumbuh seperti garis: stabil & dapat diprediksi.
Pencarian linear bekerja pada DAFTAR APAPUN, diurutkan atau tidak. Itu membuatnya sederhana. Tetapi bisa menjadi lambat.
Berapa Banyak Nama?
Anda memiliki daftar kelas dari 20 nama yang ditulis dalam urutan acak.
Anda perlu menemukan nama Zoe.
Anda memeriksa nama satu per satu, dari atas daftar ke bawah.
Potong Daftar Menjadi Dua
Pencarian Biner: Lompat ke Tengah
Pencarian biner memiliki satu aturan: daftar harus diurutkan terlebih dahulu.
Jika daftar 20 nama Anda dimulai dari A hingga Z, Anda dapat menggunakan pencarian biner.
Cara kerjanya: buka ke nama di tengah (nama #10). Tanyakan: apakah Zoe sebelum atau sesudah nama ini?
Z berada di dekat akhir alfabet, jadi Zoe datang SETELAH tengah. Buang separuh pertama. Sekarang Anda hanya memiliki nama 11-20 tersisa.
Periksa tengah dari 10 nama itu (nama #15). Z datang setelah M, jadi Zoe datang setelah nama #15. Buang nama 11-14. Sekarang Anda memiliki nama 16-20.
Terus potong menjadi dua. Setiap pengecekan menghilangkan setengah dari nama yang tersisa.
| Ukuran Daftar | Pengecekan Maksimal dengan Pencarian Biner |
|---|---|
| 20 nama | paling banyak 5 pengecekan |
| 1.000 nama | paling banyak 10 pengecekan |
| 1.000.000 nama | paling banyak 20 pengecekan |
Bandingkan dengan pencarian linear pada 1.000.000 nama: rata-rata 500.000 pengecekan.
Pencarian biner memotong daftar menjadi dua setiap kali. Memotong menjadi dua berulang kali mencapai 1 dengan sangat cepat — itulah mengapa tetap sangat cepat.
Temukan 'fig' dalam Daftar Terurut
Berikut adalah daftar terurut dari 8 kata:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Anda ingin menemukan fig menggunakan pencarian biner.
Ingat: periksa tengahnya, tanyakan apakah target Anda datang sebelum atau sesudah, lalu potong daftar menjadi dua.
Menukar Tetangga ke dalam Urutan
Bubble Sort: Bandingkan Tetangga & Tukar
Bubble sort mengurutkan daftar dengan membandingkan dua item tetangga sekaligus.
Jika dua tetangga tidak terurut — tukarnya.
Terus membuat pass melalui daftar sampai tidak ada yang perlu ditukar.
Contoh: urutkan [5, 3, 8, 1]
Pass 1:
- Bandingkan 5 & 3. 5 > 3, jadi tukar → [3, 5, 8, 1]
- Bandingkan 5 & 8. 5 < 8, tidak ada tukar → [3, 5, 8, 1]
- Bandingkan 8 & 1. 8 > 1, jadi tukar → [3, 5, 1, 8]
Pass 2:
- Bandingkan 3 & 5. OK → [3, 5, 1, 8]
- Bandingkan 5 & 1. 5 > 1, tukar → [3, 1, 5, 8]
- Bandingkan 5 & 8. OK → [3, 1, 5, 8]
Pass 3:
- Bandingkan 3 & 1. 3 > 1, tukar → [1, 3, 5, 8]
- Bandingkan 3 & 5. OK. Bandingkan 5 & 8. OK.
Selesai! [1, 3, 5, 8] ✓
Perhatian: angka terbesar menggelembung ke akhir daftar pada setiap pass. Itulah cara bubble sort mendapatkan namanya.
Bubble sort bekerja. Ini bukan yang tercepat untuk daftar besar, tetapi mudah dipahami — sempurna untuk belajar.
Urutkan [4, 2, 7, 1] dengan Bubble Sort
Urutkan daftar ini menggunakan bubble sort: [4, 2, 7, 1]
Tunjukkan daftar setelah setiap pass. Hitung berapa banyak pass yang diperlukan untuk menyelesaikannya.