Bagaimana menerapkan Algoritma Pencarian Biner di Java tanpa rekursi

Implementasi berulang dari algoritme penelusuran biner populer untuk menemukan elemen dalam larik yang diurutkan.

Halo semuanya! Saya telah menerbitkan banyak artikel algoritme dan struktur data di blog saya, tetapi yang ini adalah yang pertama di sini. Dalam artikel ini, kami akan memeriksa algoritma fundamental populer untuk wawancara.

Ya, Anda menebaknya dengan benar: Anda perlu menerapkan penelusuran biner di Java, dan Anda perlu menulis algoritme penelusuran biner berulang dan rekursif.

Dalam ilmu komputer, pencarian biner, atau pencarian setengah interval, adalah algoritma bagi dan taklukkan yang menempatkan posisi item dalam array yang diurutkan. Pencarian biner bekerja dengan membandingkan nilai input dengan elemen tengah dari array.

Perbandingan menentukan apakah elemen sama dengan input, lebih kecil dari input, atau lebih besar dari input.

Ketika elemen yang dibandingkan sama dengan input, pencarian berhenti dan biasanya mengembalikan posisi elemen.

Jika elemen tidak sama dengan input, maka dilakukan perbandingan untuk menentukan apakah input lebih kecil dari atau lebih besar dari elemen.

Bergantung pada hasilnya, algoritme kemudian memulai lagi, tetapi hanya mencari bagian atas atau bawah dari elemen array.

Jika masukan tidak terletak di dalam larik, algoritme biasanya akan mengeluarkan nilai unik yang menunjukkan ini seperti -1 atau hanya melempar RuntimeException di Java seperti NoValueFoundException.

Algoritme pencarian biner biasanya membagi dua jumlah item untuk diperiksa dengan setiap iterasi yang berurutan, sehingga menemukan item yang diberikan (atau menentukan ketidakhadirannya) dalam waktu logaritmik.

Btw, jika Anda tidak terbiasa dengan algoritma pencarian dan pengurutan fundamental, maka Anda juga dapat mengikuti kursus seperti Struktur Data dan Algoritma: Menyelam Mendalam Menggunakan Java untuk mempelajari algoritma dasar.

Jika Java bukan pilihan bahasa Anda, Anda dapat menemukan lebih banyak rekomendasi untuk JavaScript dan Python di daftar kursus algoritma ini.

Btw, jika Anda lebih suka buku, saya sarankan Anda membaca buku algoritma komprehensif seperti Pengantar Algoritma oleh Thomas H. Cormen.

Berikut adalah beberapa contoh kode yang menunjukkan logika pencarian biner berulang di Java :

Implementasi Pencarian Biner di Java

Berikut adalah contoh program untuk mengimplementasikan pencarian biner di Java. Algoritma diimplementasikan secara rekursif. Selain itu, fakta menarik untuk diketahui tentang implementasi pencarian biner di Java adalah bahwa Joshua Bloch, penulis buku Effective Java yang terkenal, menulis pencarian biner di “java.util.Arrays”.

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

Itu semua tentang bagaimana mengimplementasikan pencarian biner menggunakan rekursi di Java . Bersama dengan penelusuran Linear, berikut adalah dua algoritme penelusuran penting yang Anda pelajari di kelas ilmu komputer.

Struktur data pohon pencarian biner memanfaatkan algoritma ini dan mengatur data dalam struktur hierarki sehingga Anda dapat mencari simpul mana pun dalam waktu O (logN).

Padahal, Anda harus ingat bahwa untuk menggunakan penelusuran biner, Anda memerlukan daftar atau larik yang diurutkan, jadi Anda juga perlu mempertimbangkan biaya penyortiran saat Anda mempertimbangkan untuk menggunakan algoritme penelusuran biner di dunia nyata.

Pembelajaran Lebih Lanjut

Struktur Data dan Algoritma: Penyelaman Mendalam Menggunakan Java

Algoritma dan Struktur Data - Bagian 1 dan 2

Struktur Data di Java 9 oleh Heinz Kabutz

10 buku Algoritma untuk Wawancara

10 Kursus Struktur Data dan Algoritma untuk Wawancara

5 Kursus Gratis untuk Mempelajari Struktur Data dan Algoritma

Lainnya Struktur Data dan Algoritma tutorial Anda mungkin ingin

  • Bagaimana cara menerapkan algoritma Quicksort di Jawa? (tutorial)
  • Bagaimana cara mengimplementasikan Binary Search Tree di Java? (larutan)
  • Bagaimana cara menerapkan algoritma Quicksort tanpa rekursi? (tutorial)
  • Bagaimana cara menerapkan algoritma semacam penyisipan di Java? (tutorial)
  • Bagaimana cara mengimplementasikan algoritma bubble sort di Java? (tutorial)
  • Apa perbedaan antara algoritme pengurutan berbasis Perbandingan dan Non-Perbandingan? (menjawab)
  • Bagaimana cara mengimplementasikan Bucket Sort di Java? (tutorial)
  • Bagaimana cara menerapkan Algoritma Pencarian Biner tanpa rekursi di Java? (tutorial)
  • 50+ Kursus Struktur Data dan Algoritma untuk Pemrogram (pertanyaan)

Terima kasih telah membaca artikel ini. Jika Anda menyukai artikel ini, silakan bagikan dengan teman dan kolega Anda. Jika Anda memiliki saran atau umpan balik, silakan berikan komentar.

NB - Jika Anda serius untuk meningkatkan keterampilan Algoritma Anda, menurut saya Struktur Data dan Algoritma: Menyelam Mendalam Menggunakan Java adalah yang terbaik untuk memulai.