Contoh Program Algoritma Binary Search di C++ Beserta Penjelasan

3 min read

c++

Contoh Program Algoritma Binary Search di C++ Beserta Penjelasan – ada banyak sekali algoritma sorting yang bisa kita gunakan, salah satunya adalah binary search. Algoritma sorting ini memiliki performa yang tergolong cepat jika dibanding algoritma sorting lainnya. kenapa bisa seperti itu? mari kita bahas

Pengertian Algoritma Binary Search

Binary Search adalah sebuah algoritma pencarian yang cukup cepat. algoritma ini menggunakan metode devide and conquer dimana sebuah list akan dipecah menjadi 2 bagian dan kembali menentukan nilai tengah dan membandingkannya secara terus menerus, hingga ditemukan bahwa nilai tengahnya adalah angka yang dicari.

untuk melakukan pembagian list tersebut, diperlukan sebuah angka tengah, bila angka yang dicari lebih kecil daripada angka ditengah list, maka algoritma ini akan fokus ke serangkaian index yang berada di sebelah kiri list, begitu juga sebaliknya.

untuk menjalankan algoritma ini, kita harus mengurutkan terlebih dahulu value dari array yang ingin kita cari secara ascending. untuk masalah ini, kita bisa menggunakan algoritma sorting seperti bubble sort,insertion sort atau quick sort.

algoritma pencarian ini tergolong cepat, karena pencarian tidak dilakukan secara berurutan dari awal list hingga akhir list. namun dalam penggunaannya kita perlu memastikan angka sudah tersusun secara rapih baru kita bisa menjalankan algoritma pencarian ini.

algoritma ini sangat cocok untuk digunakan pada list yang memiliki index yang banyak dibandingkan dengan list yang memiliki index sedikit.

Penjelasan algoritma Binary Search

anggap saja kita memiliki array dengan index dan value seperti dibawah,

Langkah pertama yang akan kita lakukan adalah menyusun value dari array tersebut agar tersusun secara ascending, pada kasus ini saya menggunakan algoritma bubble sort untuk menyusunnya, sehingga didapatlah susunan array seperti ini

baca juga: contoh program algoritma merge sort di c++

selanjutnya, kita baru akan memulai algoritma binary search, langkah pertama kita perlu menentukan 4 hal yaitu left,right,mid,key.

Left digunakan sebagai batas bawah pencarian. Pada langkah ini nilai left adalah index ke 0.

Right digunakan sebagai batas atas pencarian. Pada langkah ini nilai right adalah index ke 5.

Mid ditentukan otomatis dari panjang array yang kita punya, pada contoh ini ada 6 index array yang berarti nilai mid adalah 3 dan mengacu pada index ke 2 dari array yang kita punya.

Sedangkan KEY adalah nilai yang akan kita cari, anggap saja kita akan mencari angka 4 dari value array tsb.

Langkah selanjutnya kita akan menentukan apakah value array index ke mid (3) sama dengan key (4)? ternyata tidak.

lanjut, apakah array index ke mid (3) lebih kecil dari key (4)? jika iya maka kita akan mengubah parameter left menjadi mid +1. Namun jika tidak kita akan mengubah right menjadi mid -1.

pada kasus ini value array ke mid lebih kecil dibanding key jadi kita akan mengubah left menjadi mid+1 yaitu 2+1 = 3.

Jadi saat ini array kita tinggal tersisa

kita akan mengulang lagi algoritmanya, kali ini nilai tengahnya adalah array index ke 4.

apakah array index ke 4 (5) sama dengan key (4)? ternyata tidak.

lanjut,apakah array index ke 4 (5) lebih kecil daripada key (4)? ternyata tidak, jadi kita akan mengubah nilai right menjadi mid-1 yaitu 3. sehingga sisa List kita hanya tersisa 1 yaitu array index ke 3 dengan value 4.

saat ini right dan left berada di satu tempat, sehingga nilai left,right dan mid berada pada satu posisi.

sampai di tahap ini kita akan kembali mengecek, apakah array index ke mid (4) sama dengan key (4). jika iya maka algoritma selesai dijalankan dan hasil pencarian bernilai true.

namun jika ternyata sampai di sini key masih belum ketemu, maka posisi left atau right akan kembali berubah, dan pastinya left menjadi lebih besar daripada right maka algoritma akan berhenti dan hasil pencarian dianggap false (tidak ketemu).

baca juga: Contoh Program Algoritma Sequential Search

Contoh Program Algoritma Binary Search di C++

Penjelasan

Line 3-14 : Algoritma Binary Search sesuai dengan yang dijelaskan diatas.

Line 16-33 : Algoritma Bubble Sort, selengkapnya kamu bisa baca disini

Line 35-42 : Disini kita menyiapkan array yang akan disort. pertama kita meminta user memasukan berapa panjang array yang akan dibuat di variable n, lalu kita akan membuat array dengan variable a sebanyak n. Setelah itu kita akan melakukan looping untuk memasukan value di setiap index array.

Line 43-44 : Disini kita meminta user untuk memasukan angka yang ingin dicari yang akan disimpan didalam variable key.

Line 46 : Disini kita akan menjalankan algoritma bubble sort dengan mengirimkan array dan variable n. setelah selesai array akan kembali disimpan kedalam variable a.

Line 47-51 : disini kita menjalankan algoritma binary sort, dengan mingirimkan 4 parameter yaitu: array,left,right dan n. hasilnya akan disimpan di variable res dan mengelarkan output, apakah hasil pencarian bernilai true atau false.

Output

contoh program algoritma binary search di c++

Kelebihan Algoritma Binary Search

  • Performa lebih cepat jika dibandingkan dengan algoritma search lainnya, seperti sequential search, Linier Search,dll.
  • Algoritma pencarian yang tergolong sederhana dan cepat, terlebih lagi jika index array ada banyak.
  • Sering digunakan dalam kehidupan sehari hari (contohnya diperpustakaan).

Kelemahan Algoritma Binary Search

  • Sebelum memulai proses searching, List harus diurutkan terlebih dahulu.
  • Tidak terlalu efektif jika digunakan pada List dengan banyak index dan semua elemennya tidak terurut.
  • Tidak bisa diterapkan untuk mencari string.

itulah Contoh Program Algoritma Binary Search di c++, semoga bermanfaat dan dapat menambah wawasan, kamu juga bisa mempelajari algoritma C++ lainnya disini. sampai jumpa di Tutorial C++ lainnya.

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *