Algoritma Binary Search di C++

Dec 26, 2024

—

Binary Search adalah algoritma pencarian efisien yang digunakan untuk menemukan posisi elemen dalam array terurut (ascending atau descending). Algoritma ini bekerja dengan cara membagi array menjadi dua bagian pada setiap langkah hingga elemen yang dicari ditemukan.

Cara Kerja Binary Search

Tentukan indeks awal (low) dan indeks akhir (high) array.
Hitung indeks tengah (mid) sebagai (low+high)/2
Bandingkan elemen di indeks tengah:
- Jika elemen tengah sama dengan target, pencarian selesai.
- Jika target lebih kecil, fokuskan pencarian ke bagian kiri (update high = mid - 1).
- Jika target lebih besar, fokuskan pencarian ke bagian kanan (update low = mid + 1).
Ulangi langkah 2 dan 3 hingga elemen ditemukan atau array tidak memiliki elemen lagi (low > high).

Kompleksitas:

Waktu: O(log⁡n)O(\log n) (karena array dibagi dua setiap langkah).
Ruang:
- Iteratif: O(1)O(1).
- Rekursif: O(log⁡n)O(\log n) (karena tumpukan rekursi).

Implementasi Iteratif

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Hindari overflow

        if (arr[mid] == target) {
            return mid; // Elemen ditemukan
        } else if (arr[mid] < target) {
            low = mid + 1; // Cari di bagian kanan
        } else {
            high = mid - 1; // Cari di bagian kiri
        }
    }

    return -1; // Elemen tidak ditemukan
}

int main() {
    vector<int> arr = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    int target = 50;

    int result = binarySearch(arr, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Implementasi Rekursif

#include <iostream>
#include <vector>
using namespace std;

int binarySearchRecursive(const vector<int>& arr, int low, int high, int target) {
    if (low > high) {
        return -1; // Elemen tidak ditemukan
    }

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        return mid; // Elemen ditemukan
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, high, target); // Cari di bagian kanan
    } else {
        return binarySearchRecursive(arr, low, mid - 1, target); // Cari di bagian kiri
    }
}

int main() {
    vector<int> arr = {5, 15, 25, 35, 45, 55, 65};
    int target = 35;

    int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }

    return 0;
}

Penjelasan Kode

Input:
- Array harus terurut sebelum algoritma digunakan.
- target adalah elemen yang ingin dicari.
Iteratif:
- Menggunakan loop while untuk mengurangi ukuran jangkauan pencarian.
- Tidak memerlukan tumpukan rekursi, sehingga hemat ruang.
Rekursif:
- Fungsi dipanggil secara rekursif dengan mempersempit jangkauan pencarian (low dan high).
- Memanfaatkan struktur rekursi untuk menyederhanakan logika.
Optimasi:
- mid=low+(high−low)/2 digunakan untuk menghindari overflow pada penghitungan indeks tengah.

Contoh Output

Jika input array adalah {10, 20, 30, 40, 50} dan target adalah 30:

Element found at index 2

Jika target adalah 25:

Element not found

Keuntungan Binary Search

Sangat efisien untuk dataset besar.
Operasi hanya membutuhkan O(log⁡ n) waktu, jauh lebih cepat dibandingkan Linear Search O(n).

Jika Anda ingin implementasi dengan array descending, beri tahu saya! 😊