[ HTML ] [ Java ] [ Bahasa C ]


Selasa, Mei 04, 2021

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 

+ " ditemukan pada index = " 

+ res); 

else System.out.println(key 

+ " Tidak ditemukan"); 

 

}

 

}

Output
22 ditemukan pada index = 3
40 Tidak ditemukan

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 

+ " ditemukan pada index = " 

+ res); 

else System.out.println(key 

+ " Tidak ditemukan"); 

 

}

 

}

Output:
10 ditemukan pada index = 3
15 Tidak ditemukan

Cara implementasi pencarian biner 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("Elemen"

+" ditemukan pada index " 

+ result); 

}

 

}

Output:
Elemen ditemukan pada index 3

8 komentar:

  1. Bagaimana jika nilai input tidak disortir?

    BalasHapus
    Balasan
    1. Pada contoh program sebelumnya, jika list input tidak disortir, maka hasil yang diberikkan tidak terdefinisi.

      Hapus
  2. Bagaimana jika terdapat duplikat nilai pada array? pada contoh program sorting?

    BalasHapus
    Balasan
    1. Jika terdapat nilai duplikat, maka tidak ada jaminan nilai mana yang akan ditemukan.

      Hapus
  3. Bagaimana cara Collections.binarySearch bekerja pada LinkedList?

    BalasHapus
    Balasan
    1. 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.

      Hapus
  4. Apa nilai signifikan dari nilai negatif yang dikembalikan oleh kedua fungsi?

    BalasHapus
    Balasan
    1. 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.

      Hapus

Respon komentar 7 x 24 jam, so please be patient :D