Berhenti begitu ketemu

Loop yang berhenti karena berhasil, bukan karena datanya habis, dan cara menjawab ketika tidak ada.

Sebaiknya baca lebih dulu: Mencari terkecil dan terbesar.

Berhenti di halaman yang dicari

Dua hal baru sekaligus. Pertama, loop yang berhenti karena berhasil. Sampai sekarang setiap loop berhenti karena datanya habis atau nilainya mencapai batas; di sini ia berhenti karena tujuannya sudah tercapai. Kedua, cara menjawab ketika tidak ada jawaban.

Berhenti lebih awal

SET hasil = -1
SET i = 0
WHILE i < LENGTH(numbers) AND hasil == -1
  IF numbers[i] == target
    SET hasil = i
  END
  SET i = i + 1
END
OUTPUT hasil
Kondisinya memuat dua hal: masih ada elemen, DAN belum ditemukan. Penanda hasil bekerja sekaligus sebagai jawaban dan sebagai alasan berhenti.

IngatSatu variabel dapat menjadi jawaban sekaligus penanda berhenti. Itu bukan kebetulan yang rapi, melainkan sebabnya nilai penandanya harus tidak mungkin menjadi jawaban yang sah.

Kalimat di atas menjelaskan mengapa penandanya negatif satu dan bukan nol. Nol adalah indeks yang sah, yaitu indeks elemen pertama, jadi kondisi berhenti tidak akan dapat membedakan belum ditemukan dari ditemukan di posisi pertama. Negatif satu tidak akan pernah menjadi indeks yang sah, dan itu yang membuatnya dapat dipakai sebagai penanda.

Kenapa bukan nol

Penanda nol

SET hasil = 0
WHILE i < LENGTH(numbers) AND hasil == 0
  IF numbers[i] == target
    SET hasil = i
  END
  SET i = i + 1
END

Penanda negatif satu

SET hasil = -1
WHILE i < LENGTH(numbers) AND hasil == -1
  IF numbers[i] == target
    SET hasil = i
  END
  SET i = i + 1
END

Pada [8, 8] dengan target 8, kolom kiri menemukan target di indeks nol lalu menulis nol ke hasil, dan nol adalah nilai penandanya sendiri. Loop tidak berhenti, penelusuran berlanjut, dan pada akhirnya jawabannya tetap nol sehingga tampak benar. Tetapi pada array yang targetnya tidak ada, kolom kiri juga menjawab nol, dan dua keadaan yang berbeda tidak lagi dapat dibedakan dari jawabannya.

Melihat penelusuran berhenti

SET hasil = -1
SET i = 0
WHILE i < LENGTH(numbers) AND hasil == -1
  IF numbers[i] == target
    SET hasil = i
  END
  SET i = i + 1
END
OUTPUT hasil
hasil-1
i0
target8

Penanda dipasang negatif satu, artinya belum ditemukan.

Langkah 1 dari 6
numbers [4, 8, 15] dengan target 8. Perhatikan indeks 2 tidak pernah dibaca.

Kemunculan pertama, bukan terakhir

Berhenti lebih awal bukan hanya soal kecepatan; ia menentukan jawabannya. Pada [8, 8] dengan target 8, berhenti lebih awal menjawab nol, sedangkan menelusuri sampai habis tanpa berhenti akan terus menimpa hasil dan menjawab satu. Keduanya jawaban yang berbeda untuk pertanyaan yang berbeda, dan yang diminta di sini kemunculan pertama.

  • Target yang muncul dua kali menjawab indeks pertamanya.
  • Target yang tidak ada menjawab negatif satu, bukan nol dan bukan galat.
  • Array kosong menjawab negatif satu. Kondisi pertamanya sudah salah, jadi badan tidak pernah berjalan dan penandanya bertahan.

Periksa pemahaman

numbers berisi [1, 2, 3, 4, 5, 6] dengan target 6. Berapa banyak elemen yang dibaca sebelum loop berhenti?

Ringkasan

  • Loop dapat berhenti karena berhasil, bukan hanya karena datanya habis.
  • Satu variabel dapat menjadi jawaban sekaligus penanda berhenti.
  • Nilai penandanya wajib mustahil menjadi jawaban yang sah. Nol adalah indeks yang sah, jadi ia tidak dapat dipakai.
  • Berhenti lebih awal menentukan jawabannya, bukan hanya kecepatannya.
  • Keadaan terburuk pencarian berurutan adalah target yang berada di ujung, atau target yang tidak ada.