C++ Binary Search Return Index

MUAZHAN

5 min read

·

Jul 01, 2024

30

Share

Mencari Indeks dengan Binary Search di C++

Binary search adalah algoritma pencarian yang sangat efisien untuk menemukan suatu elemen dalam array yang sudah terurut. Dalam implementasinya, binary search secara berulang membagi array menjadi dua bagian dan kemudian membandingkan elemen tengah dengan elemen yang dicari. Jika elemen tengah sama dengan elemen yang dicari, maka pencarian selesai. Jika tidak, maka pencarian dilanjutkan pada bagian kiri atau kanan dari array, tergantung pada hasil perbandingan.

Dalam konteks ini, kita akan membahas bagaimana menemukan indeks elemen yang dicari dalam array menggunakan binary search di C++.

Implementasi Binary Search untuk Mencari Indeks

Berikut adalah implementasi C++ sederhana untuk melakukan binary search dan mengembalikan indeks elemen yang dicari.

#include 

using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
      return mid; // Indeks elemen ditemukan
    } else if (arr[mid] < target) {
      left = mid + 1; // Cari di sebelah kanan
    } else {
      right = mid - 1; // Cari di sebelah kiri
    }
  }

  return -1; // Elemen tidak ditemukan
}

int main() {
  int arr[] = {2, 5, 7, 8, 11, 12};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 11;

  int index = binarySearch(arr, 0, n - 1, target);

  if (index != -1) {
    cout << "Elemen ditemukan pada indeks: " << index << endl;
  } else {
    cout << "Elemen tidak ditemukan" << endl;
  }

  return 0;
}

Kode di atas melakukan hal berikut:

1. binarySearch(int arr[], int left, int right, int target): Fungsi ini menerima array terurut arr, batas kiri (left) dan kanan (right) dari array, dan target yang dicari.
2. while (left <= right): Loop ini terus berjalan sampai batas kiri dan kanan bertemu.
3. int mid = left + (right - left) / 2;: Menghitung indeks tengah dari array.
4. if (arr[mid] == target): Memeriksa apakah elemen tengah sama dengan target. Jika ya, maka indeks mid dikembalikan.
5. else if (arr[mid] < target): Jika elemen tengah lebih kecil dari target, pencarian dilanjutkan pada bagian kanan array (left = mid + 1;).
6. else: Jika elemen tengah lebih besar dari target, pencarian dilanjutkan pada bagian kiri array (right = mid - 1;).
7. return -1;: Jika loop selesai tanpa menemukan target, fungsi mengembalikan -1 untuk mengindikasikan bahwa elemen tidak ditemukan.

Keterangan

• Array Terurut: Binary search hanya berfungsi pada array yang sudah terurut. Pastikan array yang akan dicari sudah terurut sebelum menggunakan fungsi binarySearch.
• Pengembalian Indeks: Fungsi binarySearch mengembalikan indeks elemen yang dicari dalam array. Jika elemen tidak ditemukan, fungsi mengembalikan -1.
• Kompleksitas Waktu: Binary search memiliki kompleksitas waktu logaritmik (O(log n)), yang membuatnya sangat efisien untuk mencari elemen dalam array yang besar.

Kesimpulan

Binary search adalah teknik yang sangat efisien untuk mencari elemen dalam array terurut. Dalam implementasinya di C++, fungsi binarySearch dapat digunakan untuk mencari indeks dari elemen target dalam array. Fungsi ini mengembalikan indeks jika elemen ditemukan, dan -1 jika tidak.