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
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]
• TENGAH1 = [(1 + 9) / 2 ] = 5 Kcari : K tengah1 49 > 38
AWAL = TENGAH1 + 1 = 6
• TENGAH2 = [(6 + 9) / 2 ] = 7 Kcari : K tengah2 49 > 38
AWAL = TENGAH21 + 1 = 8
TENGAH3 = [ (8 + 9 ) / 2 ] = 8 Kcari : K tengah2 49 = 49
Ketemu, Probe = 3
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 <>
a[ i ] = new Integer( i * 2 );
for( int i = 0; i <>2; i++ )
System.out.println( "Found " + i + " at " +
binarySearch( a, new Integer( i ) ) );
}
}
{
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 <>
a[ i ] = new Integer( i * 2 );
for( int i = 0; i <>2; i++ )
System.out.println( "Found " + i + " at " +
binarySearch( a, new Integer( i ) ) );
}
}
Contoh Flowchart Program Binary Search :
Maaf, mau tanya
Kalo penerapan binary search di sistem informasi akademik bagusnya mencari apa ya?