Program Binary Search

Pencarian biner adalah algoritma untuk mencari posisi elemen pada daftar yang telah diurutkan.

Pada contoh pertama berikut ini akan dicari rekaman dengan kunci 49.

Bilangan yang dicetak tebal menunjukkan rekaman yang sedang dibandingkan dan tanda kurung membatasi bagian berkas yang tersisa yang masih harus diperbandingkan. Tanda [ untuk AWAL dan tanda ] untuk AKHIR.
Download materi ini

              1          2          3          4          5          6          7          8          9

            [21       25        28        33        38        39        48        49        69]

             21       25        28        33        38        [39       48        49        69]

             21       25        28        33        38        39        48        [49       69]

•         TENGAH₁ = [(1 + 9) / 2 ] = 5             K_cari  : K _tengah1                  49 > 38

            AWAL = TENGAH₁ + 1 = 6

•         TENGAH₂ = [(6 + 9) / 2 ] = 7             K_cari  : K _tengah2                  49 > 38

            AWAL = TENGAH2₁ + 1 = 8

            TENGAH₃ = [ (8 + 9 ) / 2 ] = 8           K_cari  : K _tengah2                    49 = 49

                                                                        Ketemu, Probe = 3

Contoh kode program Binary Search :

public class BinarySearch
{
    public static final int NOT_FOUND = -1;     
    public static int binarySearch( Comparable [ ] a, Comparable x )
    {
        int low = 0;
        int high = a.length - 1;
        int mid;
        while( low <= high )
        {
            mid = ( low + high ) / 2;
            if( a[ mid ].compareTo( x ) < 0 )
                low = mid + 1;
            else if( a[ mid ].compareTo( x ) > 0 )
                high = mid - 1;
            else
                return mid;
        }
        return NOT_FOUND;     // NOT_FOUND = -1
    }
    // Test program
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [ ] a = new Integer [ SIZE ];
        for( int i = 0; i < SIZE; i++ )
            a[ i ] = new Integer( i * 2 );
        for( int i = 0; i < SIZE * 2; i++ )
            System.out.println( "Found " + i + " at " +
                                 binarySearch( a, new Integer( i ) ) );
    }
}

Contoh Flowchart Program Binary Search :

Download materi ini