Ichlasul Affan, M.Kom.

Video ini membahas implementasi Binary Search menggunakan rekursi. Binary Search digunakan untuk mencari elemen dalam list yang terurut secara ascending. Dengan rekursi, pencarian dapat dilakukan dengan lebih efisien dibandingkan dengan pendekatan iteratif. Proses pencarian dilakukan dengan membagi list menjadi dua bagian dan membandingkan elemen tengah dengan elemen yang dicari. Jika elemen tengah kurang dari elemen yang dicari, pencarian dilakukan di sisi kanan, dan sebaliknya. Meskipun Binary Search dapat diimplementasikan secara iteratif, pendekatan rekursif seringkali lebih intuitif dan efisien dalam kasus list terurut.

Oke nah sekarang kita redo lagi nih yang contoh lain ya kita praktis yang lain

yang memenuhi tips yang sebelumnya di video sebelumnya sudah disebutkan.

Maksudnya apa? Nah tips yang nomor 4 terutama yang tadi ya yaitu kalau misalkan kita temukan kasus-kasus

yang ternyata oh bisa lebih singkat nih lebih cepat dikerjakan lewat rekursif

step yang dibutuhkan rekursif step yang dibutuhkan lebih dikit daripada versi iteratifnya

maka gunakan rekursif gitu. Itu akan lebih baik gitu ya.

Let's assume you have a list of ascendingly sorted integers.

Ascendingly sorted artinya dari kecil ke besar jadi integer bilangan bulat

terurut ya list isinya bilangan bulat doang gak ada float disini

yang terurut dari kecil ke besar kalau dilihat disini 1,3,5,6,7,8,10,12,15,19 gitu.

Nah kita mau mencari satu bilangan, bilangan n disini misalkan bilangan 3

ada gak sih bilangan 3 ini ada di list ini? Kalau ada dia mengembalikan true kalau enggak dia mengembalikan false.

Nah sekarang gimana caranya? Kita masuk dulu ke yang biasa yang iteratif dulu ya.

Sesuai biasa bahwa misalkan yaudah gini misalkan dia listnya targetnya ini

maka dia akan mengembalikan ini mungkin bukan ini ya soalnya kembaliannya cuma true atau false.

Item in list gitu ya kalau misalkan itemnya sesuai dengan targetnya maka kembalikan true.

Atau misalkan simple, simple nya gini aja oh enggak enggak usah ini aja else return false.

Gitu ya ini kelihatannya simple banget nih tapi nanti kita lihat apakah secara readability ini simple banget gitu ya.

Apakah kita akan membutuhkan recursive? Jawabannya adalah iya.

Kenapa? Karena nanti kita coba nih kasus cara-cara saya ya.

Coba misalkan kita ambil di tengah, misalkan kita ambil di tengah 8 misalkan.

Tengah-tengahnya berapa nih? Ini kan 10 ya 10 list isinya 10, 10 elemen.

Kalau 10 elemen kita ambil tengah-tengahnya 10 bagi 2 deh 5 ya.

Nah 5 misalkan kita ambil index ke 5 berarti kan 0, 1, 2, 3, 4, 5 ya berarti yang 8 ini.

Nah 8 ini kita cek misalkan kita mencari 12 nih misalkan kita mencari 12 ya.

8 kan enggak sama dengan 12 ya kita cek nih 12 itu lebih besar atau lebih kecil dari 8?

Jawabannya adalah lebih besar kan 12 lebih besar dari 8.

Maka kalau lebih besar dari 8 kita ambilnya sisi kanan dari 8.

Ini yang kita jadikan bahan argumen untuk recursive berikutnya.

Untuk recursive step berikutnya 10, 12, 15, 19 gitu ya yang di sisi kanannya aja.

Nah kalau iteratif kan kita looping dari kiri ke kanan kan.

Nah oke kemudian 12 oke posisinya dimana nih 10, 12, 15, 19 ada 4 ya bagi 2, 2.

Kita ambil index ke 2, 15, 12 lebih kecil dari 15?

Ya 12 lebih kecil dari 15 maka nanti berikutnya yang diambil adalah dari 10 sampai sebelum 15.

10, 12 gitu ya 10, 12 kita bagi 2 lagi ya kita cek tengahnya lagi.

Ya kebetulan cuma ada 2 kan tengahnya ya mungkin ambil yang kanan lah 12.

12 ternyata sama nih yaudah langsung balikin aja.

Ini kita peragain lagi ya dari awal ya mungkin untuk ini ya.

Kita peragakan dari awal di ini untuk ini ya di VSCode.

1, 2, 3, ini berapa? 1, 2, 3, oh 1, 3, 5, 5, 6, 7, 8, 10, 12, 15, 19.

Ini ada 10 ya kita mau cari endnya sama dengan 12 gitu.

Nah step 1 berarti ambil tengahnya 8 gitu ya.

Step 2 kita cek tengah kita cek ini berarti berikutnya.

Step 1 kita cek ambilnya buat step 2 nanti ceknya berarti nextnya ambil 10, 12, 15, 19 nah gitu.

Nah step 2 kita cek disini tengahnya berapa? 15 nextnya 10, 12, 12 nextnya 12 kayak gitu.

Yaudah berarti sebenarnya kita technically butuh 3 step doang malahan ini bukan step ini step 0 sebenarnya.

Step 0 karena dia udah dari awal jadi kita butuh 3 kali recursive doang disini.

Gitu dan cuma butuh 3 kali recursive doang.

Bandingin dengan nanti ya nanti kita coba bandingkan ya.

Pertanyaannya sekarang gimana cara nodingnya?

Kemudian berarti kita loopingnya kita tentukan dulu base case nya.

Base case nya akan terjadi kita coba cek ya base case nya akan terjadi kalau base case nya akan terjadi kalau apa?

Pertama listnya kosong, kalau listnya kosong kembaliannya apa?

Ya nggak ketemu kan apa yang mau dicari dari list kosong?

Nggak ada kan yaudah kembaliannya otomatis false.

Base case keduanya adalah kalau misalkan list 1 elemen cek elemen sama dengan N gitu ya.

Nah recursive nya recursive case nya adalah kita milihin mau ke kiri atau mau ke kanan.

Mau ambil sebelah kirinya dari tengah atau sebelah kanannya dari tengah.

Nah ketemu base case nya sekarang kita coding base case nya.

If 0 dia return false kalau misalkan sekarang listnya 1 return ini gitu.

Nah mid disini ada tengah-tengahnya ada LST bagi 2 ya kita tengah ya bagi 2.

Karena ya kalau index di list kan nggak mungkin pakai float ya.

Nggak akan bisa karena index di list itu integer gitu.

Kalau misalkan udah base case berikutnya ya kalau misalkan udah langsung ketemu yaudah gitu.

Kalau misalkan dia kurang dari N dalam arti kalau misalkan bilangan N nya lebih besar daripada yang tengahnya.

Misalkan kayak tadi contohnya 8 kurang dari 12 berarti otomatis karena dia terurut dari kecil ke besar ya kan.

Karena dia terurut dari kecil ke besar pasti 12 itu ada di sisi kanan dari 8.

Makanya ketika kita mengecilkan ukuran dari listnya yang akan dijadikan bahan untuk rekursi berikutnya

maka kita start dari mid plus 1 mulai dari setah mid.

Else dia return dari awal sampai sebelum mid.

Setelah itu ya nah ini kita coba kan print.