Pencarian Biner di JavaScript

Pencarian biner adalah algoritma pencarian yang digunakan untuk menemukan posisi elemen tertentu dalam daftar yang diurutkan. Ia bekerja dengan berulang kali membagi daftar menjadi dua, sampai elemen yang diinginkan ditemukan atau ditentukan bahwa elemen tersebut tidak ada dalam daftar.

Bagaimana cara kerja pencarian biner?

Untuk memahami cara kerja pencarian biner, mari pertimbangkan sebuah contoh. Misalkan kita memiliki daftar bilangan bulat yang diurutkan dan kita ingin mencari posisi angka 37. Begini cara kerja algoritma pencarian biner:

1. Pertama, kami menentukan elemen tengah daftar. Jika elemen tengah adalah 37, kami selesai dan kami mengembalikan posisi elemen.
2. Jika elemen tengah bukan 37, kita periksa apakah lebih besar atau kurang dari 37. Jika lebih besar dari 37, kita tahu bahwa elemen yang diinginkan harus berada di bagian kiri daftar. Jika kurang dari 37, kita tahu bahwa elemen yang diinginkan harus berada di bagian kanan daftar.
3. Kami mengulangi proses pada bagian yang sesuai dari daftar sampai elemen ditemukan atau ditentukan bahwa elemen tersebut tidak ada dalam daftar.

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

Mengapa kita harus menggunakan pencarian biner?

Jadi, mengapa kita harus menggunakan pencarian biner? Salah satu keuntungan utama dari pencarian biner adalah kompleksitas waktunya. Dalam skenario terburuk, kompleksitas waktu pencarian biner adalah O(log n), yang berarti jauh lebih cepat daripada pencarian linier (O(n)) untuk daftar besar. Ini menjadikannya algoritme yang efisien untuk mencari kumpulan data besar.

Kesimpulannya, pencarian biner adalah algoritma yang berguna untuk menemukan posisi elemen tertentu dengan cepat dalam daftar yang diurutkan. Kompleksitas waktunya membuatnya cocok untuk mencari dataset besar, dan relatif mudah diimplementasikan dalam JavaScript.