Algoritma dan coding Binary Searching dengan Java

   Algoritma dan coding Binary Searching dengan Java

Binary Searching merupakan salah satu metode pencarian yang kompleksitasnya cukup baik untuk melakukan pencarian data. Ada banyak metode pencarian yang ada namun, pada kesempatan ini saya akan bahas bagaimana algoritma dari Binary Searching. Pada dasarnya perhitungan pencarian Binary Searching cukup gampang dilakukan karena, sekumpulan data tersebut di urutkan terlebih dahulu secara Ascending kemudian, untuk melakukan pencariannya tiap iterasi membagi banyaknya data yang ada sehingga ditemukanlah data yang dicari. Agak bingung ya? hehehe.... langsung masuk ke contoh kasusnya aja ya. :D

Contoh Kasus:

Terdapat sekumpulan data dengan nilai sebagai berikut.

[5, 2, 9, 15, 0, 6, 10]

Lakukanlah proses pencarian Data yang bernilai 15 dengan menggunakan metode Binary Searching.

Jawab:

1. Langkah pertama, urutkan terlebih dahulu data yang ada secara Ascending sehingga menghasilkan output sebagai berikut [0, 2, 5, 6, 9, 10, 15].
2. Kemudian, buatlah tabel seperti berikut.
   
3. Sebelum masuk ke langkah perhitungannya perhatikan rumus berikut.
   - Jika value < cari xss=removed> - Jika value > cari maka, akhir = tengah - 1
   - Jika value == cari maka, pencarian berakhir
4. Sekarang saatnya untuk masuk ke proses Binary Searching.

Proses Binary Searching:

• Iterasi 1
  Awal: 0 --> (ingat, bahwa ini nilai index bukan nilai data dan tiap iterasi 1 pasti Awal == 0)
  Akhir: 6 --> (nilai index yang terakhir. Perhatikan tabel sebelumnya)
  Tengah: (Awal + Akhir) / 2 = (0 + 6) / 2 = 6 / 2 = 3
  Value: Index 3 = 6 --> (Index 3 == 6. Perhatikan tabel sebelumnya. nilai 3 itu didapat dari Nilai Tengah)
  Cek: 6 < 15> (berarti, value < cari xss=removed>
• Iterasi 2
  Awal: 3 + 1 = 4 (3 merupakan nilai Tengah sebelumnya. Lihat rumus diatas dan proses iterasi sebelumnya)
  Akhir: 6 (Tetap 6)
  Tengah: (Awal + Akhir) / 2 = (4 + 6) / 2 = 10 / 2 = 5
  Value: Index 5 = 10 (Perhatikan tabel sebelumnya)
  Cek: 10 < 15> (berarti, value < cari xss=removed>
• Iterasi 3
  Awal: 5 + 1 = 6
  Akhir: 6 (Ingat, nilai Akhir akan berubah apabila rumus value > cari terpenuhi)
  Tengah: (Awal + Akhir) / 2 = (6 + 6) / 2 = 12 / 2 = 6
  Value: Index 6 = 15
  Cek: 15 == 15 (value == cari. Hore,,,  akhirnya ketemu data yang dicari. Data ditemukan pada iterasi 3).

Langkah diatas dapat Anda lihat lebih simple dalam bentuk tabel berikut.

Gimana? Mudah bukan ? Ok, sekarang kita lanjut contoh kasus yang lain lagi ya. Masih tetap menggunakan Data yang sama namun, kali ini kita mau mencari Data yang bernilai 5.

Jawab:

1. Sorting Data secara Ascending sehingga outputnya menjadi[0, 2, 5, 6, 9, 10, 15].
2. Buat tabel seperti berikut.
   
3. Lanjut ke Proses Binary Searching.

Proses Binary Searching

• Iterasi 1
  Awal: 0
  Akhir: 6
  Tengah: 3
  Value: Index 3 = 6
  Cek: 6 > 5 (value > cari maka, pada iterasi berikutnya nilai Akhir = Tengah - 1)
• Iterasi 2
  Awal: 0
  Akhir: 3 - 1 = 2
  Tengah: 1
  Value: Index 1 = 2
  Cek: 2 < 5>Awal = Tengah + 1)
• Iterasi 3
  Awal: 1 + 1 = 2
  Akhir: 2
  Tengah: 2
  Value: Index 2 = 5
  Cek: 5 == 5 (value == cari. Data ditemukan pada iterasi 3)

Gimana? masih bisa Anda ikuti kan tutorial ini. Awas pusing ya.... hehehe.....

Sekarang gimana kalau misalnya Data yang dicari itu memang tidak ada atau tidak ditemukan. Dalam ilmu pemrograman ini sering disebut dengan istilah Best Case(Kasus Terbaik) dan Worst Case(Kasus Terburuk). Dalam binary searching, jika Data yang dicari tidak ditemukan maka, Data tersebut worst case namun, apabila Data tersebut ditemukan pada iterasi pertama maka, Data tersebut merupakan best case.

Lanjut contoh kasus lagi ya apabila Data yang dicari tidak ditemukan. Masih tetap menggunakan Data yang sama dan Data yang dicari data yang bernilai 12.

Jawab:

1. Sorting terlebih dahulu Data tersebut secara Ascending sehingga outputnya menjadi [0, 2, 5, 6, 9, 10, 15].
2. Buatlah tabel seperti berikut.
   
3. Lanjut ke Proses Binary Searching.

Proses Binary Searching

• Iterasi 1
  Awal: 0
  Akhir: 6
  Tengah: 3
  Value: Index 3 = 6
  Cek: 6 < 12>Awal = Tengah + 1)
• Iterasi 2
  Awal: 3 + 1 = 4
  Akhir: 6
  Tengah: 5
  Value: Index 5 = 10
  Cek: 10 < 12>Awal = Tengah + 1)
• Iterasi 3
  Awal: 5 + 1 = 6
  Akhir: 6
  Tengah: 6
  Value: Index 6 = 15
  Cek: 15 > 12 (value > cari maka, pada iterasi berikutnya Akhir = Tengah - 1)
• Iterasi 4
  Awal: 6
  Akhir: 6 - 1 = 5
  Tengah: 5 ( (6 + 5) / 2 = 11 / 2 = 5 --> hitung integer atau tanpa koma)
  Value: Index 5 = 10
  Cek: 10 < 12>Awal = Tengah + 1)
• Iterasi 5
  Awal: 5 + 1 = 6
  Akhir: 5
  Tengah: 5
  Value: Index 5 = 10
  Cek: 10 < 12>Awal = Tengah + 1)
• Iterasi 6
  Awal: 5 + 1 = 6
  Akhir: 5
  Tengah: 5
  Value: Index 5 = 10
  Cek: 10 < 12>Awal = Tengah + 1)

Dah gitu - gitu aja terus proses iterasi berikutnya karena, nilai yang dicari memang tidak ditemukan maka, diakhir proses binary searching akan terus melakukan perulangan yang sama secara terus menerus dengan nilai yang sama sehingga system akan error. Namun, dalam program hal itu bisa Anda hindari dengan memberi batasan perulangannya apabila terjadi worst case seperti contoh kasus diatas.

Berikut source code nya di Java.

import java.util.Scanner;

/**
 * 
 * @author Yudi Setiawan
 *
 */

public class MetodeBinarySearching
{
    public static int[] data = null;
    public static int awal, tengah, akhir, temp, count;

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);

        //  Input jumlah data
        System.out.print("Jumlah data : ");     
        int jlh = scan.nextInt();

        //  Input tiap nilai dan simpan ke array
        data = new int[jlh];
        for(int x = 0; x < data xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed> cari
            else if(data[tengah] > cari)
            {
                System.out.print(iterasi+"   ");
                System.out.print(awal+"   ");
                System.out.print(akhir+"   ");
                System.out.print(tengah+"   ");
                System.out.print(data[tengah]+"\n");
                akhir = tengah - 1;
            }

            //  Cek Worst Case
            if(temp != data[tengah])
                temp = data[tengah];
            else
                count++;

            //  batasan untuk worst case
            if(count == 3)
                break;
        }

        //  Output
        if(temu == true)
            System.out.println("\nData "+cari+" ditemukan pada index ke-"+tengah+"\n"+
            "dan Iterasi ke-"+iterasi);

        else
            System.out.println("\nData "+cari+" tidak ditemukan");

    }

    //  Sorting Ascending
    public static void sorting()
    {
        int temp = 0;
        for(int x = 0; x < data xss=removed xss=removed xss=removed xss=removed xss=removed>

Berikut output dari source code diatas.



 
                                                            java
                                                    

Share on Facebook Share on Twitter

https://agungss1.blogspot.com