Menerapkan Algoritma Array
| English | Bahasa Indonesia |
|---|---|
| traversal/træˈvɜːsl/ | penelusuran |
| index/ˈɪndeks/ | indeks |
| linear search/ˈlɪnɪə sɜːtʃ/ | pencarian linear |
Algoritma array standar
- Sebagian besar tugas array adalah traversing ditambah salah satu dari beberapa pola standar.
- Jumlah / rata-rata: akumulasikan total, lalu bagi dengan
length. - Hitung: tingkatkan ketika elemen cocok dengan kondisi.
- Min / max: lacak nilai terkecil atau terbesar yang terlihat sejauh ini.
Menemukan maksimum
- Mulai
max = a[0](elemen pertama), lalu traverse dari indeks1. if (a[i] > max) { max = a[i]; }di dalam perulangan.- Setelah perulangan,
maxmenyimpan nilai terbesar dalam array. - Mulai dari elemen pertama, bukan
0—0bisa lebih besar dari semua nilai.
Pencarian nilai
- Untuk memeriksa apakah suatu nilai ada, traverse dan bandingkan setiap elemen.
- Kembalikan indeks di mana itu ditemukan, atau
-1jika perulangan selesai tanpa kecocokan. if (a[i] == target) return i;di dalam perulangan;return -1;setelahnya.- Ini adalah pencarian linear (Unit 4.14 membahasnya secara mendalam).
Pergeseran dan modifikasi
- Beberapa algoritma memindahkan atau mengubah elemen — mis. geserkan semuanya ke kiri, atau gandakan setiap nilai.
- Memodifikasi memerlukan perulangan terindeks agar Anda dapat mengonversi
a[i] = .... - Waspadai batas saat membaca
a[i+1]— indeks terakhir tidak memiliki tetangga. - Jejakkan indeks dengan cermat untuk menghindari akses di luar batas.
Inisialisasi pencarian min/max dengan elemen PERTAMA, bukan 0. int max = 0; gagal jika setiap nilai negatif (akan melaporkan 0 secara salah). Gunakan int max = a[0]; dan mulai perulangan pada indeks 1. Dan ketika algoritma membaca a[i+1], hentikan perulangan di i < a.length - 1, atau iterasi terakhir akan membaca melampaui akhir.
Menemukan maksimum dari a:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- Untuk
a = {3, 9, 5}: max menjadi9.
Algoritma array menggabungkan traversing dengan pola: jumlah/rata-rata, hitung, min/max, atau pencarian (kembalikan indeks atau -1). Inisialisasikan min/max dengan elemen pertama, bukan 0. Memodifikasi elemen memerlukan perulangan terindeks, dan membaca a[i+1] memerlukan batas yang lebih ketat untuk tetap dalam jangkauan.
Menemukan nilai maksimum
max dimulai dari a[0]=3, menjadi 9, lalu tetap (a = {3,9,5}).
Untuk menemukan maksimum dari sebuah array, Anda harus menginisialisasi max ke...
Memulai dari 0 gagal jika semua nilai negatif.
Untuk a = {3, 9, 5}, berapakah nilai maksimum?
9 adalah elemen terbesar.
Pencarian linear mengembalikan apa jika target tidak ditemukan?
Secara konvensi, -1 berarti 'tidak ditemukan'.
Algoritma yang membaca a[i+1] harus looping selama...
Berhenti satu langkah lebih awal menjaga a[i+1] tetap dalam batas.
Memodifikasi elemen array (a[i] = ...) memerlukan loop berindeks, bukan for-each.
for-each tidak bisa menulis kembali ke dalam array.