Algoritma - Pencarian Biner

Binary search atau pencarian biner merupakan algoritma pencarian cepat dengan running time kompleksitas Ο atau log n. Kita pernah membahas sekilas tentang pencarian biner ini pada materi klasifikasi urutan pertumbuhan, dimana dilakukan metode pengembangan model matematika untuk menggambarkan kinerja melalui suatu algoritma, dengan array of integers yang terurut. Algoritma pada pencarian biner bekerja berdasarkan prinsip membagi dan menaklukkan dengan array yang sudah dalam keadaan urut. apabila data belum dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam pendekatan ini indeks elemen x ditentukan ketika elemen tersebut termasuk dalam daftar elemen. Jika array tidak disortir, pencarian linear digunakan untuk menentukan posisi.

Ketika daftar disortir, maka model matematika pada teknik pencarian biner ini digunakan untuk menemukan item dalam daftar. Prosedur yang dilakukan dengan menggunakan seluruh daftar yang dibagi menjadi dua sub-daftar. Jika item ditemukan di posisi tengah maka akan mengembalikannya kelokasi, namun jika melompat ke sub-daftar kiri atau kanan dan melakukan proses yang sama lagi hingga menemukan item atau melebihi rentang.

Singkatnya seperti ini Untuk melakukan binary search: Pencarian biner haruslah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Metode ini untuk memperkecil jumlah operasi perbandingan yang anda dilakukan pada data yang dicari dengan data yang ada di dalam tabel, apalagi jika jumlah datanya sangat besar ukurannya. Kemudian melakukan proses pembagian ruang pencarian yang dilakukan dengan berulang-ulang sampai data ditemukan dan bisa saja terjadi dimana ruang pencarian tidak dapat dibagi lagi, maka ini artinya data not found.

Algoritmanya seperti ini:

  • binarySearch (array, start, end, key).
  • Input: Array yang diurutkan, lokasi awal dan akhir, dan tombol pencarian.
  • Output: lokasi kunci (jika ditemukan), jika tidak salah lokasi.

Mula-mula anda ambil posisi awal 0 dan posisi akhir = N - 1, lalu carilah posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2. Setelah itu data yang dicari kemudian dibandingkan dengan data tengah. Jika hasilnya lebih kecil, maka proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1. Namun Jika hasil lebih besar ditemukan, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama dengan yang dicari.

Contohnya seperti ini: Anda ingin mencari data 17 pada data berikut:

binarysearch1

Awalnya setelah data disortir dan diurutkan, cari data tengah (0+9)/2 = 4. (0 adalah posisi awal sedangkan 9 adalah posisi akhir= N-1, 10-1). Berarti data tengahnya adalah data ke-4 atau 14. Sedangkan data yang dicari adalah 17, sekarang bandingkan dengan data tengah (14) diperoleh 17 > 14, artinya proses dilanjutkan tapi rumus posisi awal menjadi (posisi tengah + 1) diperoleh 4+1=5.

binarysearch2

Data tengah yang baru adalah (5+9)/2 = data ke -7, atau data tengahnya adalah 24. Data yang dicari adalah 17, jika dibandingkan data tengah 17 < 24. Proses mesti lanjut lagi dengan posisi akhir menjadi = posisi tengah – 1 ( 7-1 = data ke-6 ).

binarysearch3

Data tengah yang baru, (5+6)/2 = 5, berarti data tengah yang baru adalah data ke-5 atau 17. Bandingkan dengan data yang mau dicari yaitu 17, dan hasilnya 17=17, data ditemukan. Binary search akan berakhir ketika data yang ditemukan atau posisi awal lebih besar daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi akhir berarti data not found

Penulisan programnya seperti ini:

  • (BA = BATAS AWAL = POSISI AWAL)
  • (BB = BATAS BAWAH = POSISI AKHIR)
  1. BA ← 0
  2. BB ← N - 1
  3. Result ← false
  4. Jika (BA <= BB) dan (tidak ketemu) Proses lanjutkan lagi pada baris 5 sampai dengan 8
  5. x ← (BA + BB) / 2
  6. Jika (Data[x] = y) maka found ← true
  7. Jika (y < Data[x]) maka BB ← m – 1
  8. Jika (y > Data[x]) maka BA ← m + 1
  9. Jika (found) maka x adalah indeks dari data yang dicari, jika tidak data not found
int BinarySearch(int A)
{
  int BA = 0, BB = Max-1, x;
  bool found = false;
  while((BA <= BB) && (!found))
  {
      x = (BA + BB) / 2;
      if(Data[x] == A)
        found = true;
      else if (A < data[x])
        BB = x - 1;
      else
        BA = x + 1;
  }
  if(found)
    return x;
  else
    return -1;
}