Binary Search ~ Pemrograman dan Teknologi

Binary search digunakan untuk melakukan pencarian di dalam array yang sudah terurut nilainya. Pencarian dengan binary search relatif lebih cepat dibandingkan dengan pencarian biasa yang mengecek seluruh Array.

Pencarian dilakukan dengan mencari titik tengah setelah ujung kiri dan kanan ditentukan. Titik tengah dijadikan ujung yang baru berdasarkan perbandingannya dengan nilai yang yang dicari. Pencarian akan dihentikan jika data di tengah sama dengan nilai yang dicari.

int binary_search(int arr[], int kiri, int kanan, int x){
int tengah;
int pos=-1;
    while(kanan >= kiri) {
            tengah = kiri + (kanan - kiri) / 2;
            if (arr[tengah] == x){
                pos=tengah;
                break;
            }else if (arr[tengah] > x){
                kanan=tengah - 1;
            }else kiri=tengah + 1;
    }
    return pos;
}

Beberapa contoh mungkin menggunakan rekursi untuk menerapkan binary_search. Tapi, kenyataannya binary search bisa diterapkan hanya dengan loop menggunakan while seperti dalam function di atas.

#include <stdio.h>
#include <stdlib.h>

int binary_search(int arr[], int kiri, int kanan, int x){
int tengah;
int pos=-1;
    while(kanan >= kiri) {
            tengah = kiri + (kanan - kiri) / 2;
            if (arr[tengah] == x){
                pos=tengah;
                break;
            }else if (arr[tengah] > x){
                kanan=tengah - 1;
            }else kiri=tengah + 1;
    }
    return pos;
}

int cmpf (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

int main(void){
    int arr[] = { 12, 13, 14, 20, 40 };
    int n=sizeof(arr)/sizeof(int);
    int nilai;
    qsort(arr, n, sizeof(int), cmpf);
    
    printf("Data : ");
    for(int i=0;i<n;i++)printf("%d ", arr[i]);
    printf("\nCari : ");scanf("%d", &nilai);
    int hasil = binary_search(arr, 0, n - 1, nilai);
    
    (hasil < 0)
        ? printf("Elemen tidak ditemukan")
        : printf("Elemen ditemukan dengan indeks %d", hasil);

    return 0;
}

Contoh

Data : 12 13 14 20 40
Cari : 14
Element ditemukan dengan indeks 2

Contoh di atas mengurutkan data di dalam array dengan qsort bawaan Bahasa C walaupun itu sebenarnya tidak diperlukan karena data sudah terurut. Kalian hanya akan memerlukan pengurutan jika data belum terurut. Hasil dari binary search kemungkinan besar akan tidak sesuai jika data belum terurut.