Jawaban dan Penjelasan:

Algoritma Pencarian

Pencarian Linier (Linear Search)

Pencarian linier dilakukan dengan membandingkan elemen data yang dicari dengan setiap elemen pada list/array data, mulai dari elemen pertama hingga elemen terakhir.
Pada pencarian linier, array data tidak perlu terurut terlebih dahulu.

Algoritma Pencarian Linier

Misalkan elemen data yang dicari adalah x, dan data disimpan dalam array data[] dengan banyak elemen n.
⇒ Elemen pertama pada array data adalah data[0] (seperti pada bahasa pemrograman C, C++, Java, Python, dll.)
⇒ Elemen terakhir pada array data adalah data[n–1].

ALGORITMA

Looping/Iterasi dari i = 0 hingga i = n–1:

1. Jika data[i] = x, maka x ditemukan pada data[i].
   ⇒ Proses selesai, algoritma mengembalikan/menghasilkan nilai i.
2. x tidak ditemukan pada array data, maka algoritma mengembalikan/menghasilkan nilai –1.

ILUSTRASI

Diberikan array data = [4, 3, 5, 7, 2, 1, 6, 9]
⇒ n = 8

Yang dicari: 1 ⇒ x = 1

Tahapan algoritma:

1. i = 0
   data[0] = 4 ≠ 1
2. i = 1
   data[1] = 3 ≠ 1
3. i = 2
   data[3] = 5 ≠ 1
4. i = 3
   data[3] = 7 ≠ 1
5. i = 4
   data[4] = 2 ≠ 1
6. i = 5
   data[5] = 1 = 1
7. Selesai.
   ⇒ Nilai yang dikembalikan (return value): 5
   ⇒ x berada pada data[5] (elemen ke-6 pada array data).

________________

Pencarian Biner (Binary Search)

Pada pencarian biner, array data masukan harus sudah terurut. Algoritma ini membandingkan nilai yang dicari dengan elemen tengah dari array data.

• Jika nilai yang dicari sama dengan elemen tengah dari array data, maka algoritma selesai, dan mengembalikan indeks elemen tengah.
• Jika nilai yang dicari lebih dari elemen tengah dari array data, maka ulangi pencarian pada subarray kanan dari array data, yaitu subarray di sebelah kanan elemen tengah.
• Jika nilai yang dicari kurang dari elemen tengah dari array data, maka ulangi pencarian pada subarray kiri dari array data, yaitu subarray di sebelah kiri elemen tengah.

Algoritma Pencarian Biner

Misalkan elemen data yang dicari adalah x, dan data disimpan dalam array data[] yang sudah terurut, dengan banyak elemen n.
⇒ Elemen pertama pada array data adalah data[0] (seperti pada bahasa pemrograman C, C++, Java, Python, dll.)
⇒ Elemen terakhir pada array data adalah data[n–1].

ALGORITMA

1. atas = n–1, bawah = 0
2. tengah = (atas + bawah) div 2
   (pembagian bilangan bulat, contohnya 6 div 2 = 3, 7 div 2 = 3)
3. Jika x = data[tengah], maka proses selesai, algoritma mengembalikan nilai variabel tengah.
4. Sebaliknya, jika x ≠ data[tengah], namun x > data[tengah], maka:
   ⇒ bawah = tengah + 1
   ⇒ ulangi langkah ke-2
5. Selebihnya, yaitu  jika x ≠ data[tengah], namun x < data[tengah], maka:
   ⇒ atas = tengah – 1
   ⇒ ulangi langkah ke-2

ILUSTRASI

Diberikan array data = [4, 3, 5, 7, 2, 1, 6, 9]
⇒ n = 8

Data terurut = [1, 2, 3, 4, 5, 6, 7, 9]

Yang dicari: 1 ⇒ x = 1

Tahapan algoritma:

1. atas = 8–1 = 7, bawah = 0
2. tengah = (0+7) div 2 = 3
3. 1 < data[3] = 4
   ⇒ atas = 3–1 = 2
4. tengah = (0+2) div 2 = 1
5. 1 < data[1] = 2
   ⇒ atas = 2–1 = 1
6. tengah = (0+1) div 2 = 0
7. 1 = data[0] = 1
8. Selesai.
   ⇒ Nilai yang dikembalikan (return value): 0
   ⇒ x berada pada data[0] (elemen pertama pada data yang sudah terurut).

________________

Salah satu hal yang perlu diperhatikanadalahalgoritma pencarian biner menerima masukan list/array data yang sudah terurut. Sedangkan algoritma pencarian linier dapat diterapkan pada list/array data asli, baik yang belum terurut atau sudah terurut.