Algoritma Binary Search C++

MUAZHAN

5 min read

·

Jun 28, 2024

27

Share

Algoritma Binary Search dalam C++

Algoritma binary search adalah teknik pencarian yang efisien untuk menemukan suatu elemen dalam array yang terurut. Algoritma ini bekerja dengan membagi array menjadi dua bagian dan membandingkan elemen tengah dengan nilai yang dicari. Jika nilai yang dicari lebih kecil dari elemen tengah, pencarian dilanjutkan di bagian kiri array. Sebaliknya, jika nilai yang dicari lebih besar dari elemen tengah, pencarian dilanjutkan di bagian kanan array. Proses ini berulang hingga nilai yang dicari ditemukan atau array habis.

Berikut adalah langkah-langkah implementasi binary search dalam C++:

1. Inisialisasi variabel:
   • low: Indeks awal array.
   • high: Indeks akhir array.
   • mid: Indeks tengah array.
2. Perulangan:
   • Menghitung mid sebagai rata-rata low dan high.
   • Membandingkan nilai pada mid dengan nilai yang dicari.
     • Jika nilai pada mid sama dengan nilai yang dicari, pencarian selesai dan nilai mid dikembalikan.
     • Jika nilai yang dicari lebih kecil dari nilai pada mid, high diatur ke mid - 1.
     • Jika nilai yang dicari lebih besar dari nilai pada mid, low diatur ke mid + 1.
3. Keluaran:
   • Jika nilai yang dicari ditemukan, fungsi mengembalikan indeks elemen tersebut.
   • Jika nilai yang dicari tidak ditemukan, fungsi mengembalikan -1.

Berikut adalah contoh implementasi binary search dalam C++:

#include 

using namespace std;

int binarySearch(int arr[], int n, int x) {
  int low = 0;
  int high = n - 1;
  
  while (low <= high) {
    int mid = low + (high - low) / 2; // Menghitung mid
    
    if (arr[mid] == x) {
      return mid; // Nilai ditemukan
    } else if (arr[mid] < x) {
      low = mid + 1; // Cari di bagian kanan
    } else {
      high = mid - 1; // Cari di bagian kiri
    }
  }
  
  return -1; // Nilai tidak ditemukan
}

int main() {
  int arr[] = {2, 3, 4, 10, 40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  
  int result = binarySearch(arr, n, x);
  
  if (result == -1) {
    cout << "Nilai " << x << " tidak ditemukan" << endl;
  } else {
    cout << "Nilai " << x << " ditemukan pada indeks " << result << endl;
  }
  
  return 0;
}

Kode di atas menunjukkan implementasi binary search untuk menemukan nilai 10 dalam array arr. Fungsi binarySearch menerima array, ukuran array, dan nilai yang dicari sebagai parameter. Fungsi tersebut mengembalikan indeks elemen jika nilai ditemukan, dan -1 jika tidak ditemukan.

Keunggulan Binary Search

Binary search memiliki beberapa keunggulan dibandingkan dengan algoritma pencarian lainnya, seperti pencarian linier:

• Efisiensi waktu: Binary search memiliki kompleksitas waktu logaritmik (O(log n)), yang berarti waktu yang dibutuhkan untuk mencari suatu elemen meningkat secara logaritmik seiring dengan bertambahnya ukuran array. Hal ini membuatnya jauh lebih efisien dibandingkan dengan pencarian linier yang memiliki kompleksitas waktu linear (O(n)).
• Cocok untuk data yang terurut: Binary search dirancang untuk bekerja dengan data yang terurut. Jika data tidak terurut, binary search tidak dapat digunakan dan harus diganti dengan algoritma pencarian lainnya.

Kesimpulan

Algoritma binary search adalah teknik pencarian yang sangat efisien untuk data yang terurut. Kecepatan dan kompleksitas waktunya yang rendah menjadikannya pilihan yang tepat untuk berbagai aplikasi, seperti pencarian data dalam basis data, pencarian kata dalam kamus, dan lain sebagainya.