Lompat ke konten Lompat ke sidebar Lompat ke footer

Program Pencarian pada Java Menggunakan Binary Search

Dalam pengembangan perangkat lunak, seringkali pengembang dihadapkan pada kebutuhan untuk mencari elemen tertentu dalam sebuah kumpulan data yang terurut. Salah satu algoritma pencarian yang paling efisien adalah algoritma Binary Search. Artikel ini akan menjelaskan konsep dasar Binary Search dan bagaimana pengembang dapat menerapkannya dalam sebuah program Java.


Sebelum lebih lanjut mempelajari materi tentang Program Pencarian pada Java Menggunakan Binary Search, terlebih dahulu pelajari materi tentang: Menggunakan Underscore Untuk Nama Variabel Java dan Fungsinya, Fungsi Currying Java dan Penerapannya, dan Menggunakan Underscore Java untuk Literasi Angka.

Pemahaman

Binary Search adalah algoritma pencarian yang efisien untuk mencari nilai tertentu dalam sebuah array atau kumpulan data terurut. Algoritma ini bekerja dengan membagi kumpulan data menjadi dua bagian dan memeriksa elemen tengahnya. Jika nilai yang dicari kurang dari elemen tengah, maka pencarian dilanjutkan hanya pada setengah kiri kumpulan data. Begitu juga sebaliknya, jika nilai yang dicari lebih besar dari elemen tengah, maka pencarian dilanjutkan hanya pada setengah kanan kumpulan data. Proses ini diulang secara rekursif hingga nilai yang dicari ditemukan atau kumpulan data telah habis.

Ada dua cara untuk menggunakan binary search pada Java, pertama dengan menggunakan fungsi Array.binarysearch() dan kedua dengan menggunakan fungsi Collectiontion.binarysearch(). Kedua cara tersebut akan dijelaskan menggunakan contoh yang akan dijelaskan sebagai berikut.

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

Contoh:

// Program Java

// mendemonstrasikan kerja

// dari Arrays.binarySearch()

// pada sortir array

import java.util.Arrays

 

public class MKN

 

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

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

Contoh:

// Program Java

// mendemonstrasikan fungsi

// dari

// Collections.binarySearch() 

import java.util.List

import java.util.ArrayList

import java.util.Collections

 

public class MKN 

 

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

Contoh: 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

Contoh: Berikut adalah contoh implementasi algoritma Binary Search dalam bahasa pemrograman Java.

public class BinarySearch {


public static int 

binarySearch(int[] arr, int 

target

{

int left = 0;

int right = arr.length - 1;


while (left <= right) 

{

int mid = left 

+ (right 

- left) / 2;


if (arr[mid] == target) 

{return mid;} 

else 

if (arr[mid] < target) 

{left = mid + 1;} 

else {right = mid - 1;}

}


return -1

// Nilai tidak ditemukan

}


public static void main(String[] args

{

int[] array = {

2, 4, 6, 8, 10, 12, 14, 16

};


int target = 10;

int result

binarySearch(array, target);


if (result != -1

{System.out.println("Elemen ditemukan di indeks: " + result);} 

else 

{System.out.println("Elemen tidak ditemukan dalam array.");}

}


}

Dalam kode yang diberikan sebelumnya, pengembang memiliki metode binarySearch yang menerima sebuah array terurut dan nilai target yang ingin dicari. Metode ini kemudian menggunakan algoritma Binary Search untuk mencari nilai target dalam array tersebut.

Analisis Kinerja

Keuntungan utama dari Binary Search adalah kompleksitas waktu yang rendah, yaitu O(log n), di mana n adalah jumlah elemen dalam array. Ini membuatnya sangat efisien, terutama untuk kumpulan data yang besar.

Namun, untuk menggunakan Binary Search, kumpulan data harus terurut terlebih dahulu. Jika kumpulan data tidak terurut, diperlukan waktu tambahan untuk mengurutkannya terlebih dahulu, yang bisa membuat proses pencarian menjadi kurang efisien.

Kelebihan dari algoritma Binary Search dalam mencari elemen dalam kumpulan data terurut:
  • Kompleksitas Waktu yang Rendah: Salah satu keunggulan utama dari Binary Search adalah kompleksitas waktu yang rendah. Algoritma ini memiliki kompleksitas waktu O(log n), di mana n adalah jumlah elemen dalam kumpulan data. Ini berarti waktu yang dibutuhkan untuk menemukan nilai dalam kumpulan data meningkat secara logaritmik dengan jumlah elemen. Dibandingkan dengan metode pencarian linear, yang memiliki kompleksitas waktu O(n) di mana pencarian dilakukan dengan memeriksa setiap elemen secara berurutan, Binary Search jauh lebih cepat, terutama untuk kumpulan data besar.
  • Efisiensi dalam Pencarian Data Terurut: Binary Search bekerja secara efisien pada kumpulan data yang telah diurutkan terlebih dahulu. Karena algoritma ini membagi kumpulan data menjadi dua bagian setiap kali, proses pencarian dapat dilakukan secara iteratif atau rekursif dengan mengurangi jumlah elemen yang harus diperiksa pada setiap langkah. Ini membuatnya ideal untuk pencarian dalam struktur data seperti array atau daftar yang telah diurutkan sebelumnya.
  • Kemampuan Menangani Kumpulan Data Besar: Karena kompleksitas waktu Binary Search tidak terlalu dipengaruhi oleh jumlah elemen dalam kumpulan data, algoritma ini sangat efisien untuk menangani kumpulan data yang besar. Bahkan dengan penambahan jumlah elemen yang signifikan, waktu yang dibutuhkan untuk menemukan nilai tetap relatif singkat dan konsisten.
  • Penggunaan yang Luas: Algoritma Binary Search digunakan secara luas dalam berbagai aplikasi dan domain. Ini digunakan dalam pemrograman komputer, pemrosesan data, analisis algoritma, dan banyak lagi. Kemampuannya untuk dengan cepat menemukan nilai dalam kumpulan data besar membuatnya menjadi pilihan yang populer di banyak aplikasi yang membutuhkan pencarian efisien.

Dengan kelebihan-kelebihannya yang signifikan dalam hal kompleksitas waktu, efisiensi dalam pencarian data terurut, kemampuan menangani kumpulan data besar, dan penggunaan yang luas, algoritma Binary Search merupakan pilihan yang kuat untuk pencarian nilai dalam kumpulan data terurut dalam konteks pengembangan perangkat lunak dan analisis data.

Kesimpulan

Algoritma Binary Search adalah salah satu algoritma pencarian yang paling efisien dalam menemukan nilai tertentu dalam sebuah kumpulan data terurut. Dengan implementasi yang tepat dalam bahasa pemrograman Java, pengembang dapat dengan mudah menggunakan algoritma ini dalam pengembangan perangkat lunak. Dengan kompleksitas waktu yang rendah, Binary Search adalah pilihan yang baik untuk mencari nilai dalam kumpulan data yang besar dengan cepat dan efisien.

Referensi Tambahan:

Artikel ini didedikasikan kepada: Asti Diah Safitri, Ayu Nur Jannah, Clarinet Rachma Devie, Devy Maria Kristiani, dan Diana Hidayati Utami.

11 komentar untuk "Program Pencarian pada Java Menggunakan Binary Search"

  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
  5. Kenapa kodenya tidak bisa menemukan elemen first(0), sudah saya coba tapi hasilnya malah return -1.

    BalasHapus
    Balasan
    1. Coba dengan array berikut pada kode binary search -{11, 10, 110, 11, 23, 21}. Kemungkinan tidak akan error.

      Permasalahan yang sering terjadi biasanya, karena nilai array yang diberikan terlalu singkat. Jadi solusinya, adalah dengan melakukan penambahan Arrays.sort(arr) pada method binarySearch.

      Hapus
    2. Saya rasa harus dilakukan pengurutan array terlebih dahulu jika ingin menambahkan angka lain ke dalam array tersebut, jika tidak kemungkinan kode program tersebut tidak akan berfungsi.

      Hapus

Hubungi admin melalui Wa : +62-896-2414-6106

Respon komentar 7 x 24 jam, mohon bersabar jika komentar tidak langsung dipublikasi atau mendapatkan balasan secara langsung.

Bantu admin meningkatkan kualitas blog dengan melaporkan berbagai permasalahan seperti typo, link bermasalah, dan lain sebagainya melalui kolom komentar.

- Ikatlah Ilmu dengan Memostingkannya -
- Big things start from small things -