C++ Binary Search Stl

MUAZHAN

3 min read

·

Jul 01, 2024

21

Share

Pencarian Biner dengan STL C++

Pencarian biner merupakan algoritma pencarian yang sangat efisien untuk menemukan suatu nilai dalam array yang sudah terurut. Algoritma ini bekerja dengan membagi array menjadi dua bagian, lalu membandingkan nilai target dengan nilai tengah array. Jika nilai target sama dengan nilai tengah, pencarian selesai. Jika nilai target lebih kecil dari nilai tengah, pencarian dilanjutkan pada bagian kiri array. Sebaliknya, jika nilai target lebih besar dari nilai tengah, pencarian dilanjutkan pada bagian kanan array.

C++ menyediakan library STL (Standard Template Library) yang memudahkan kita dalam mengimplementasikan algoritma pencarian biner. Library ini menawarkan fungsi std::binary_search yang dapat digunakan untuk melakukan pencarian biner pada array yang sudah terurut.

Cara Menggunakan std::binary_search

Fungsi std::binary_search menerima tiga parameter:

1. first: Iterator ke elemen pertama array.
2. last: Iterator ke elemen terakhir array.
3. value: Nilai yang dicari.

Fungsi ini mengembalikan nilai boolean (true jika nilai ditemukan, false jika tidak ditemukan).

Berikut contoh kode penggunaan std::binary_search:

#include 
#include 
#include 

using namespace std;

int main() {
  // Deklarasi array yang sudah terurut
  vector arr = {2, 5, 7, 8, 11, 12};

  // Mencari nilai 7
  if (binary_search(arr.begin(), arr.end(), 7)) {
    cout << "Nilai 7 ditemukan dalam array" << endl;
  } else {
    cout << "Nilai 7 tidak ditemukan dalam array" << endl;
  }

  // Mencari nilai 10
  if (binary_search(arr.begin(), arr.end(), 10)) {
    cout << "Nilai 10 ditemukan dalam array" << endl;
  } else {
    cout << "Nilai 10 tidak ditemukan dalam array" << endl;
  }

  return 0;
}

Kode di atas akan mencetak:

Nilai 7 ditemukan dalam array
Nilai 10 tidak ditemukan dalam array

Keuntungan Menggunakan std::binary_search

• Mudah digunakan: Fungsi std::binary_search sangat mudah digunakan, sehingga kita tidak perlu menuliskan kode pencarian biner sendiri.
• Efisien: Pencarian biner memiliki kompleksitas waktu O(log n), yang sangat efisien untuk array besar.

Kesimpulan

std::binary_search adalah fungsi yang sangat berguna untuk mencari suatu nilai dalam array yang sudah terurut. Fungsi ini mudah digunakan, efisien, dan tersedia di library STL C++.