Latihan C++ # 53: Membuat Binary Search

Anak Males – Pada kesempatan ini, kita akan membahas salah satu algoritma pencarian yang paling keren dalam pemrograman, yaitu “Program C++ Binary Search.” Jadi, jika kamu seorang programmer atau lagi belajar bahasa pemrograman C++, topik ini pasti akan membuatmu tertarik!

Pernah gak kamu mengalami situasi di mana kamu harus mencari nilai tertentu dalam data yang super besar? Atau mungkin ingin cari data dalam data yang sudah terurut dengan cepat dan mudah? Nah, jawabannya adalah Binary Search!

Algoritma ini memang jagoan dalam mencari data dalam data yang sudah terurut dengan cepat banget. Dan nggak heran, banyak banget aplikasi dan proyek yang mengandalkan algoritma keren ini.

Di artikel ini, kita bakal jelaskan langkah demi langkah tentang konsep dan cara kerja Binary Search.

Baca : Belajar C++ #12 : Memahami Konsep Pointer & References

Kita juga akan tunjukin cara menerapkan Binary Search dalam bahasa pemrograman C++, lengkap dengan contoh-contoh asyik yang bisa bikin kamu paham dengan mudah.

Oh iya, nggak perlu khawatir kalau kamu pemula, atau malah udah punya pengalaman. Kita bakal bahas dengan bahasa yang ramah dan mudah dimengerti, jadi semua orang pasti bisa ikutan.

Yuk, kita siapin diri untuk nge-explore dunia Binary Search dalam bahasa pemrograman C++. Kamu bakal kaget sendiri dengan betapa hebatnya algoritma ini dalam menghadapi berbagai tantangan pemrograman.

Jadi, ayo kita mulai petualangan seru tentang topik “Program C++ Binary Search” ini! Siap-siap aja deh belajar dari dasar sampai tuntas bersama kita!

Apa Itu Binary Search?

Baca : Latihan C++ #25: Transpose & Determinan Matrix 3×3

Binary Search, atau yang juga dikenal dengan “Pencarian Biner,” adalah salah satu algoritma pencarian yang efisien dan kuat yang digunakan untuk mencari elemen tertentu dalam kumpulan data yang sudah terurut.

Algoritma ini beroperasi pada data terurut dan bekerja dengan membandingkan elemen tengah dalam kumpulan data dengan elemen yang sedang dicari.

Konsep dasar dari Binary Search adalah mengurangi ruang pencarian menjadi setengah setiap langkahnya. Pada setiap iterasi, algoritma akan membandingkan elemen tengah dengan nilai yang sedang dicari.

Jika nilai yang sedang dicari lebih besar dari elemen tengah, maka pencarian akan berlanjut di separuh kanan kumpulan data. Jika nilai yang sedang dicari lebih kecil dari elemen tengah, maka pencarian akan berlanjut di separuh kiri kumpulan data.

Proses ini akan terus berlanjut hingga nilai yang dicari ditemukan atau kumpulan data menyusut menjadi kosong.

Baca : Latihan C++ #36 : Belah Ketupat Bintang

Kelebihan utama dari Binary Search adalah kemampuannya untuk mencari data dalam waktu logaritmik. Artinya, pencarian dapat diselesaikan dengan cepat bahkan dalam kumpulan data yang sangat besar.

Jika dibandingkan dengan metode pencarian lainnya, seperti Linear Search yang memiliki kompleksitas waktu linear, Binary Search jauh lebih efisien.

Namun, perlu diingat bahwa agar Binary Search berfungsi dengan benar, data harus sudah dalam kondisi terurut. Jika data tidak terurut, kita perlu mengurutkannya terlebih dahulu sebelum menggunakan algoritma ini.

Meskipun Binary Search memiliki beberapa batasan, seperti kebutuhan data terurut dan tidak dapat menangani data dengan duplikat, namun algoritma ini tetap menjadi salah satu pilihan favorit para programmer dalam banyak aplikasi dan masalah pemrograman.

Program C++Binary Search

Baca : Belajar C++ #13 : Memahami Konsep Sorting Data di C++

Berikut adalah contoh program C++ untuk implementasi Binary Search. Program ini akan mencari elemen tertentu dalam sebuah array yang sudah terurut:

#include <iostream>
using namespace std;

// Fungsi Binary Search
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Elemen ditemukan, mengembalikan indeksnya
        } else if (arr[mid] < target) {
            left = mid + 1; // Pencarian dilanjutkan di sebelah kanan
        } else {
            right = mid - 1; // Pencarian dilanjutkan di sebelah kiri
        }
    }

    return -1; // Elemen tidak ditemukan, mengembalikan -1
}

int main() {
    int n;
    cout << "Masukkan jumlah elemen dalam array: ";
    cin >> n;

    int arr[n];
    cout << "Masukkan elemen array (dalam keadaan terurut):\n";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int target;
    cout << "Masukkan elemen yang ingin dicari: ";
    cin >> target;

    int result = binarySearch(arr, n, target);

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

    return 0;
}

Mari kita jelaskan baris per baris:

#include <iostream>
using namespace std;

Di baris ini, program mengimpor pustaka iostream yang diperlukan untuk operasi input-output standar. Pernyataan “using namespace std;” memungkinkan kita menggunakan fungsi-fungsi dari namespace std (seperti cout dan cin) tanpa menuliskan “std::” setiap kali.

int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Elemen ditemukan, mengembalikan indeksnya
        } else if (arr[mid] < target) {
            left = mid + 1; // Pencarian dilanjutkan di sebelah kanan
        } else {
            right = mid - 1; // Pencarian dilanjutkan di sebelah kiri
        }
    }

    return -1; // Elemen tidak ditemukan, mengembalikan -1
}

Baca : Belajar C++ #13 : Memahami Konsep Sorting Data di C++

Ini adalah definisi dari fungsi binarySearch yang menerima tiga parameter: array terurut (arr), jumlah elemen dalam array (n), dan elemen yang ingin dicari (target). Fungsi ini mengimplementasikan algoritma Binary Search.

• left dan right adalah indeks yang menunjukkan rentang pencarian saat ini dalam array.
• Selama left kurang dari atau sama dengan right, loop while akan berjalan.
• mid adalah indeks tengah dari rentang pencarian saat ini.
• Jika arr[mid] sama dengan target, berarti elemen ditemukan di indeks mid, sehingga fungsi mengembalikan mid.
• Jika arr[mid] kurang dari target, kita tahu elemen yang dicari harus berada di sebelah kanan, maka left diperbarui untuk membatasi pencarian hanya di sebelah kanan mid.
• Jika arr[mid] lebih dari target, elemen yang dicari harus berada di sebelah kiri, maka right diperbarui untuk membatasi pencarian di sebelah kiri mid.
• Jika elemen tidak ditemukan dalam rentang pencarian, loop akan berlanjut hingga left lebih besar dari right, dan pada akhirnya fungsi mengembalikan -1.

Baca : Latihan C++ # 50: Membuat Radix Sort

int main() {
    int n;
    cout << "Masukkan jumlah elemen dalam array: ";
    cin >> n;

    int arr[n];
    cout << "Masukkan elemen array (dalam keadaan terurut):\n";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int target;
    cout << "Masukkan elemen yang ingin dicari: ";
    cin >> target;

    int result = binarySearch(arr, n, target);

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

    return 0;
}

Ini adalah fungsi main, yang merupakan titik masuk program. Di sini:

• Program meminta pengguna untuk memasukkan jumlah elemen dalam array.
• Kemudian, pengguna diminta untuk memasukkan elemen-elemen array dalam keadaan terurut.
• Setelah array diisi, pengguna diminta untuk memasukkan elemen yang ingin dicari.
• Fungsi binarySearch dipanggil dengan array, jumlah elemen, dan elemen yang ingin dicari.
• Hasil pencarian disimpan dalam variabel result.
• Hasil pencarian diperiksa: jika result tidak sama dengan -1, maka elemen ditemukan dan indeksnya dicetak. Jika result adalah -1, maka elemen tidak ditemukan dicetak.
• Program mengembalikan nilai 0, menandakan bahwa program telah berakhir dengan sukses.

Semua ini digunakan untuk mengimplementasikan algoritma Binary Search dalam mencari elemen tertentu dalam array terurut dengan efisien.

Output Program C++ Binary Sort

Baca : Latihan C++ # 51: Membuat Tree Sort

Jika Anda menjalankan program di lingkungan tersebut, berikut adalah contoh output yang mungkin akan dihasilkan:

Masukkan jumlah elemen dalam array: 7
Masukkan elemen array (dalam keadaan terurut):
1 3 5 7 9 11 13
Masukkan elemen yang ingin dicari: 7
Elemen ditemukan pada indeks: 3

Namun, outputnya dapat bervariasi tergantung pada input yang Anda berikan pada saat menjalankan program. Pastikan bahwa input elemen array dimasukkan dalam keadaan terurut, karena algoritma Binary Search hanya bekerja pada array yang sudah terurut.

Baca : Latihan C++ # 52: Membuat Maximum Sort

Penutup

Dalam dunia pemrograman, algoritma merupakan inti dari pemecahan masalah. Salah satu algoritma yang sangat penting dan sering digunakan dalam mencari elemen dalam koleksi data adalah Binary Search. Binary Search merupakan metode pencarian efisien yang bekerja dengan sangat baik pada data yang telah terurut.