Binary Search pada Java

Ada dua cara untuk melakukan binary search pada Java

satu, Arrays.binarysearch() berfungsi untuk kumpulan nilai array dan juga bisa berfungsi pada tipe data primitif.

/* Program Java mendemonstrasikan kerja dari Arrays.binarySearch() pada sortir array */ import java.util.Arrays; public class GFG { public static void main(String[] args) { int arr[] = { 10, 20, 15, 22, 35 }; Arrays.sort(arr); int key = 22; int res = Arrays.binarySearch(arr, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); key = 40; res = Arrays.binarySearch(arr, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); } }

Output: 
22 found at index = 3
40 Not found

dua, Collection.binarysearch() berfungsi untuk koleksi objek data seperti ArrayList dan LinkedList.

/* Program Java mendemonstrasikan fungsi dari Collections.binarySearch() */ import java.util.List; import java.util.ArrayList; import java.util.Collections; public class GFG { public static void main(String[] args) { List<integer> al = new ArrayList<integer>(); al.add(1); al.add(2); al.add(3); al.add(10); al.add(20); /* Angka 10 disimpan pada array indeks ke 3 */ int key = 10; int res = Collections.binarySearch(al, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); key = 15; res = Collections.binarySearch(al, key); if (res >= 0) System.out.println(key + " found at index = " + res); else System.out.println(key + " Not found"); } }

Output:
10 found at index = 3
15 Not found

Bagaimana jika nilai input tidak disortir?
Jika list input tidak disortir, maka hasil yang diberikkan tidak terdefinisi.

Bagaimana jika terdapat duplikat nilai pada array?
Jika terdapat nilai duplikat, maka tidak ada jaminan nilai mana yang akan ditemukan.

Bagaimana cara Collections.binarySearch bekerja pada LinkedList?
Method Collection.binarySearch akan berjalan selama bebera waktu untuk akses random list seperti ArrayList. Jika list spesifik tidak diimplementasikan pada interface Random akses atau pada skala lebih besar, maka method ini akan melakukan iterasi berbasis pencarian biner dengan melakukan perbandingan tautan terhadap elemen yang dicari.

Apa nilai signifikan dari nilai negatif yang dikembalikan oleh kedua fungsi?
Fungsi mengembalikan indeks dari kunci pencarian jika fungsi berisi nilai array, jika tidak maka tambahkan nilai -1. Nilai yang dimasukkan didefinisikan sebagai titik dimana kata kunci (key) yang dimasukkan ke dalam array. Nilai indeks dari elemen pertama lebih besar dari key, atau panjangnya jika semua element dalam array kurang dari spesifik key. Dengan ini dijamin bahwa valued akan lebih dari 0 jika dan hanya jika key ditemukan.

Bagaimana mengimplementasikan pencarian biner yang dibuat pada Java?

/* Java implementation dari binary rekursif search */ class BinarySearch { /* mengembalikan nilai indek x pada array arr[1..r], else mengembalikan nilai -1 */ int binarySearch(int arr[], int l, int r, int x) { if (r>=l) { int mid = l + (r - l)/2; /* jika elemen ditampilkan pada mid array */ if (arr[mid] == x) return mid; /* jika elemen ditampilakn lebih kecil dari mid, maka hanya akan ditampilkan pada bagian kiri subarray */ if (arr[mid] > x) return binarySearch(arr, l, mid-1, x); /* lainnya, elemen yang ditampilkan pada bagian kanan subarray */ return binarySearch(arr, mid+1, r, x); } /* nilai -1 diberikan jika tidak ada elemen yang ditampilkan pada array */ return -1; } /* Driver method untuk menguji algoritma binary sort */ public static void main(String args[]) { BinarySearch ob = new BinarySearch(); int arr[] = {2,3,4,10,40}; int n = arr.length; int x = 10; int result = ob.binarySearch(arr,0,n-1,x); if (result == -1) System.out.println("Element not present"); else System.out.println("Element found at index " + result); } }

Output:
Element found at index 3