Algoritma Pencarian Biner di Java

1. Ikhtisar

Dalam artikel ini, kita akan membahas keuntungan dari pencarian biner dibandingkan pencarian linier sederhana dan menjalankan implementasinya di Java.

2. Perlunya Pencarian yang Efisien

Katakanlah kita berada dalam bisnis penjualan anggur dan jutaan pembeli mengunjungi aplikasi kita setiap hari.

Melalui aplikasi kami, pelanggan dapat menyaring item yang memiliki harga di bawah n dolar, memilih botol dari hasil pencarian, dan menambahkannya ke gerobaknya. Kami memiliki jutaan pengguna yang mencari anggur dengan batasan harga setiap detik. Hasilnya harus cepat.

Di bagian belakang, algoritme kami menjalankan penelusuran linier melalui seluruh daftar anggur yang membandingkan batas harga yang dimasukkan oleh pelanggan dengan harga setiap botol anggur dalam daftar.

Kemudian, ia mengembalikan barang yang memiliki harga kurang dari atau sama dengan batas harga. Pencarian linier ini memiliki kompleksitas waktu O (n) .

Artinya, semakin banyak jumlah botol wine di sistem kami, semakin banyak waktu yang dibutuhkan. Waktu pencarian meningkat secara proporsional dengan jumlah item baru yang diperkenalkan.

Jika kita mulai menyimpan item dalam urutan yang diurutkan dan mencari item menggunakan pencarian biner, kita dapat mencapai kompleksitas O (log n) .

Dengan pencarian biner, waktu yang dibutuhkan oleh hasil pencarian meningkat secara alami dengan ukuran kumpulan data, tetapi tidak secara proporsional.

3. Pencarian Biner

Sederhananya, algoritme membandingkan nilai kunci dengan elemen tengah dari array; jika tidak sama, separuh di mana kuncinya tidak dapat menjadi bagian dihilangkan, dan pencarian dilanjutkan untuk separuh yang tersisa sampai berhasil.

Ingat - aspek kuncinya di sini adalah bahwa array sudah diurutkan.

Jika pencarian berakhir dengan sisa setengah kosong, kuncinya tidak ada dalam array.

3.1. Impl. Iteratif

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

The runBinarySearchIteratively Metode mengambil sortedArray , kunci & yang rendah & tinggi indeks dari sortedArray sebagai argumen. Ketika metode berjalan untuk pertama kalinya rendah , indeks pertama dari sortedArray, adalah 0, sedangkan tinggi , indeks terakhir dari sortedArray, sama dengan panjangnya - 1.

Bagian tengah adalah indeks tengah dari sortArray . Sekarang algoritma menjalankan while loop untuk membandingkan key dengan nilai array dari indeks tengah dari sortArray .

3.2. Impl. Rekursif

Sekarang, mari kita lihat implementasi rekursif yang sederhana juga:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

The runBinarySearchRecursively Metode menerima sortedArray , kunci, yang rendah dan tinggi indeks dari sortedArray .

3.3. Menggunakan Array. binarySearch ()

int index = Arrays.binarySearch(sortedArray, key); 

SortArray dan kunci int , yang akan dicari dalam array integer, diteruskan sebagai argumen ke metode binarySearch dari kelas Java Arrays .

3.4. Menggunakan Koleksi. binarySearch ()

int index = Collections.binarySearch(sortedList, key); 

SortList & kunci Integer , yang akan dicari dalam daftar objek Integer , diteruskan sebagai argumen ke metode binarySearch dari kelas Java Collections .

3.5. Performa

Apakah akan menggunakan pendekatan rekursif atau iteratif untuk menulis algoritme sebagian besar adalah masalah preferensi pribadi. Tetapi masih ada beberapa hal yang harus kita perhatikan:

1. Rekursi bisa lebih lambat karena overhead pemeliharaan tumpukan dan biasanya membutuhkan lebih banyak memori

2. Rekursi tidak ramah tumpukan . Ini dapat menyebabkan StackOverflowException saat memproses kumpulan data besar

3. Rekursi menambahkan kejelasan pada kode karena membuatnya lebih pendek dibandingkan dengan pendekatan berulang

Idealnya, pencarian biner akan melakukan perbandingan yang lebih sedikit dibandingkan dengan pencarian linier untuk nilai n yang besar. Untuk nilai n yang lebih kecil, pencarian linier dapat bekerja lebih baik daripada pencarian biner.

Perlu diketahui bahwa analisis ini bersifat teoritis dan dapat bervariasi tergantung pada konteksnya.

Selain itu, algoritme penelusuran biner memerlukan kumpulan data yang diurutkan yang juga memerlukan biaya . Jika kita menggunakan algoritma pengurutan gabungan untuk menyortir data, kompleksitas tambahan n log n ditambahkan ke kode kita.

Jadi, pertama-tama kita perlu menganalisis persyaratan kita dengan baik dan kemudian mengambil keputusan tentang algoritma pencarian mana yang paling sesuai dengan persyaratan kita.

4. Kesimpulan

Tutorial ini mendemonstrasikan implementasi algoritme penelusuran biner dan skenario yang lebih disukai untuk digunakan daripada penelusuran linier.

Silakan temukan kode untuk tutorial di GitHub.