Mencari terkecil dan terbesar

Nilai awal pembanding tidak boleh dikarang. Ia harus datang dari data itu sendiri.

Sebaiknya baca lebih dulu: Menghitung sampai berhenti, Menunjuk elemen lewat nomornya.

Juara sementara

Itulah seluruh polanya. Simpan satu pemenang sementara, telusuri sisanya, ganti pemenangnya setiap kali ada yang lebih baik. Yang menentukan benar salahnya bukan perbandingannya, melainkan dari mana pemenang sementara pertama datang.

IngatNilai awal pembanding diambil dari elemen pertama array, bukan dari nol.

Kenapa nol membongkar sendiri

Nilai awal dikarang

SET terbesar = 0
FOR EACH angka IN numbers
  IF angka > terbesar
    SET terbesar = angka
  END
END

Nilai awal dari data

SET terbesar = numbers[0]
SET i = 1
WHILE i < LENGTH(numbers)
  IF numbers[i] > terbesar
    SET terbesar = numbers[i]
  END
  SET i = i + 1
END

Pada array [-10, -3, -50, -1] kolom kiri menjawab nol. Nol bukan anggota arraynya, tidak pernah dibandingkan dengan apa pun, dan tetap menjadi jawaban karena tidak ada satu pun angka negatif yang lebih besar darinya. Kolom kiri bekerja sempurna selama datanya memuat angka positif, dan itu yang membuat bug ini lolos dari pengujian yang tidak pernah memakai data negatif.

Perhatikan bahwa kolom kanan memulai penelusuran dari indeks satu, bukan nol. Elemen nol sudah menjadi pemenang sementara, dan membandingkannya dengan dirinya sendiri tidak salah tetapi juga tidak berguna. Yang penting: kalau penelusurannya dimulai dari nol, hasilnya tetap benar. Ini bukan kesalahan, hanya satu perbandingan yang terbuang.

Satu lintasan, dua jawaban

Terkecil dan terbesar dapat dicari bersamaan dalam satu penelusuran. Dua pemenang sementara, dua perbandingan per elemen, tetapi arraynya hanya dibaca sekali. Menelusuri dua kali juga menghasilkan jawaban yang benar; yang dihemat waktu, dan pada array besar penghematan itu berarti.

SET terkecil = numbers[0]
SET terbesar = numbers[0]
SET i = 1
WHILE i < LENGTH(numbers)
  IF numbers[i] < terkecil
    SET terkecil = numbers[i]
  END
  IF numbers[i] > terbesar
    SET terbesar = numbers[i]
  END
  SET i = i + 1
END
terkecil-10
terbesar-10
i1

Keduanya dimulai dari elemen pertama, yaitu negatif sepuluh. Bukan dari nol.

Langkah 1 dari 5
numbers berisi [-10, -3, -50, -1]. Perhatikan keduanya dimulai dari elemen pertama, dan terbesar hanya berganti sekali.

Array yang terlalu kecil, dan yang seragam

  • Array kosong tidak punya ekstrem sama sekali, jadi jawabannya kosong. Ini bukan nol, dan bukan galat: pertanyaan mana yang terbesar pada kumpulan tanpa anggota tidak punya jawaban.
  • Array berisi satu elemen menjawab elemen itu dua kali. Ia sekaligus terkecil dan terbesar, dan itu jawaban yang benar bukan tanda ada yang salah.
  • Array yang seluruh elemennya sama, misalnya [3, 3, 3], menjawab tiga dan tiga. Tidak satu pun perbandingan pernah bernilai benar, dan pemenang sementaranya tidak pernah berganti.

Array kosong adalah alasan mengapa mengambil nilai awal dari data menuntut penjaga. Membaca numbers[0] pada array kosong adalah membaca indeks yang tidak ada, tepat persoalan pelajaran 4.1. Jadi urutannya: tolak array kosong lebih dulu dengan klausa penjaga, baru ambil elemen pertama.

Periksa pemahaman

Kode memakai nilai awal terkecil bernilai nol pada array [3, 3, 3]. Apa jawabannya?

Ringkasan

  • Simpan pemenang sementara, telusuri sisanya, ganti bila ada yang lebih baik.
  • Nilai awal pembanding wajib datang dari data, bukan dikarang.
  • Nilai awal yang dikarang selalu salah pada salah satu arah pencarian.
  • Array kosong wajib ditolak lebih dulu, sebab membaca elemen pertamanya adalah membaca indeks yang tidak ada.
  • Satu elemen sekaligus terkecil dan terbesar.
  • Terkecil dan terbesar dapat dicari dalam satu lintasan, dan pada array besar itu berarti.