binary search

Jika kita mempunyai sebuah file dari record-record yang telah dijalankan,

kita dapat melanjutkan menghapuskan memory pemeriksaan yang diperlukan

untuk mendapatkan kembali sebuah record yang telah dipakai oleh suatu teknik

binary search.

Suatu binary search dibandingkan dengan kunci dari pencarian record dengan

record tengah dari sebuah file. Kemudian masing-masing pencarian record

yang telah ditempatkan atau setengah dari file yang telah dihilangkan dengan

pertimbangan yang lebih lanjut. Dalam kasus yang sebelumnya, proses pemban-

dingan dari record tengah dilanjutkan dalam record-record selanjutnya.

Jika kita harus menghilangkan bagian atas dari sebuah file termasuk

record yang telah dibandingkan berlawanan. Selanjutnya jika kita harus

menghilangkan bagian bawah dari sebuah file termasuk record yang telah

dibandingkan berlawanan. Dalam pengulangan proses dari pembandingan

berlawanan dari record tengah, kita akhirnya akan menempatkan record yang

kita inginkan atau menentukan bahwa itu tidak ada dalam file ketika tidak

ada record-record selanjutnya.

Algorithm 2.1

Binary Search.

Terendah = 1.

Tertinggi = n.

While terendah < tertinggi do.

Tengah = (terendah + tertinggi) / 2.

if nilai kunci = nilai (tengah). Then data ditemukan.

Else if nilai kunci > nilai (tengah). Then terendah = tengah + 1.

Else tertinggi = tengah - 1.

end

end

end

Mari kita amati sebuah contoh dari suatu binary search yang telah disajikan terhadap suatu file dari record-record yang telah disusun secara urut. Dalam contoh ini, kita mencari record-record dengan kunci 39, dimana berindikasikan record yang terbaru yang telah dibandingkan berlawanan dari tanda kurung besar membatasi record yang masih dibawah pertimbangan.

Contoh 1

Di bawah ini adalah kunci–kunci carilah kunci 39 dengan mengunakan algorithm Binary Search.

[13, 16, 18, 27, 28, 29, 38, 39, 53].

1 2 3 4 5 6 7 8 9

File ini dinamakan File Sequential (secara berurutan).

Cara penyelesaian.

Bila di cari kunci 39 maka ;

Bila terendah = 1, dan tertinggi = 9,

maka 1 + 9 = 10 , lalu 10 / 2 = 5.

1. Nomor urut 5, adalah kunci 28 , tapi 28 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 5 , dan tertinggi = 9,

maka : 5 + 9 = 14

14 / 2 = 7.

2. Nomor urut 7 adalah 38 , tapi 38 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 8, dan tertinggi = 9, (karena mid + 1 jadi 7+1=8)

maka : 8 + 9 = 17

17 / 2 = 8,5 => 8,5 ≈ 8

Note: kl mengambil kebawah, haruskonsisten untuk jawaban selanjutnya jika ada kasus yg sama juga harus kebawah

3. Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.

[13, 16, 18, 27, 28, 29, 38, 39, 53]

Contoh 2

Ada 2000 kunci Mahasiswa AKAKOM dengana mengunakan Algoritma Binary Search. Carilah kunci 1345

Cara penyelesaian.

1. pergi ke tengah yaitu ; record dengan kunci 1000.
2. pergi ke record tengah pada separuh bagian ke-dua yaitu ; record sementara (1001+2000)/2 ketemu 1500, maka Record yang di cari ada diantara 1001- 1500.
3. pergi ke bagian tengah antara (1001+1499)/2, yaitu ; record 1250. Record yang dicari 1345 > 1250 berarti ada di antara 1250 - 1499.
4. pergi ke bagian tengah antara (1251+1499)/2 , yaitu ; 1375. Record yang di cari 1345 < 1375 , berarti ada di antara 1251 - 1274.
5. pergi ke bagian tengah antara (1251+1374)/2 atau 1312,5. Record yang di cari 1345 > 1312 , berarti ada di antara 1313 - 1374.
6. pergi ke-bagian tengah antara (1313+1374)/2 atau 1343,5. Record yang di cari 1345 > 1343, berarti ada di antara 1344 –1374.
7. pergi ke-bagian tengah antara (1344+1374)/2 atau 1359. Record yang di cari 1345 < 1359, berarti ada di antara 1334 – 1358.
8. pergi ke-bagian tengah antara (1344+1358)/2 atau 1351. Record yang di cari 1345 < 1351, berarti ada di antara 1344 – 1350.
9. pergi ke-bagian tengah antara (1344+1350)/2, atau 1347. Record yang di cari 1345 < 1347, berarti ada di antara 1344 – 1346.
10. pergi ke bagian tengah antara (1344+1346)/2, atau 1345. Record yang di cari1345 = 1345, ketemu.

Contoh 3

Dari data berikut gunakanlah metode binary search

Cari nomer kunci dari 232 , sedangkan jumlah seluruh mahasiswa sebanyak 700 orang.

Pembahasaan :

(1 + 700)/2 = 350

angka 350 lebih besar dari 232, maka kita harus mencarinya kembali.

(1+ 349)/2 = 175

angka 175 lebih kecil dari 232, maka kita akan mencari kembali

(176 + 349)/2 = 262

angka 362 lebih besar dari 232, maka kita akan melakukan pencarian lagi.

(176 + 261)/2 = 218

angka 218 lebih kecil dari 232 maka dicari lagi

(219 + 261)/2 = 240

angka 240 lebih besar dari 232, maka akan dicari lagi

(219 + 239)/2 = 229

angka 229 lebih kecil dari 232, maka akan dicari lagi

(230 + 239)/2 = 234

angka 234 lebih besar dari 232, maka akan dicari lagi

(230 + 233)/2 = 231

angka 231 lebih kecil dari 232, maka

(232 + 233)/2 = 232

sudah ditemukan

contoh 4

Di bawah ini adalah kunci–kunci carilah kunci 17 dan 39 dengan mengunakan algorithm Binary Search.

[13, 16, 18, 27, 28, 29, 38, 39, 53].

Jawab :

File ini dinamakan File Sequential (secara berurutan).

Cara penyelesaian.

Bila di cari kunci 39 maka

Bila terendah = 1, dan tertinggi = 9,

maka 1 + 9 = 10 , lalu 10 / 2 = 5

1· Nomor urut 5, adalah kunci 28 , tapi 28 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 6, dan tertinggi = 9

maka 6 + 9 = 15 lalu 15 / 2 = 7

2· Nomor urut 7 adalah 38 , tapi 38 < 39,

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 8, dan tertinggi = 9,

maka 8 + 9 = 17, lalu 17 / 2 = 8.

3· Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.

[13, 16, 18, 27, 28, 29, 38, 39, 53]

Contoh 5

Dari daftar kunci berikut

2,5,11,12,14,19,30,32,41,42,47,49,51,52

Dicari suatu kunci 12 dan 42, tentukan pencarian tersebut dengan metode binary search

Cara penyelesaian.

Jika kita hendak mencari suatu kunci dari daftar berikut maka terlebih dahulu kita harus mengetahui daftar tertinggi dan daftar terendah jadi langkah pertama yang harus di ambil, yaitu :

1· mencari kunci dari angka 12 maka :

nilai terendah = 1 dan nilai tertinggi = 14

maka 1 + 14 = 15, lalu 15/2 = 7,5

2· karena nomer urut 7 adalah 30, maka 30 > 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 1, dan nilai tertinggi adalah = 7

sehingga didapat : 1 + 6 = 7, lalu 7 / 2 = 3.

3· karena nomer urut dari nomer 3 adalah 11, maka 11 < 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 4, dan nilai tertinggi adalah = 6

sehingga didapat : 4 + 6 = 10, lalu 10 / 2 = 5.

4· karena nomer urut dari nomer 5 adalah 14, maka 14 > 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 4, dan nilai tertinggi adalah = 4

sehingga didapat : 4 + 4 = 8, lalu 8 / 2 = 4.

nomer 4 adalah kunci dari nomer 12, dimana kunci 12 = 12. ketemu

Untuk mencari kunci nomer 42 dengan methode Binary Search, maka :

1. dari daftar dibawah ini dapat kita lihat bahwa :

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

didapat nilai terendah = 1, dan nilai tertinggi = 14

hingga di dapat : 1 + 14 = 15, lalu 15 / 2 = 7,5

2. karena nomer urut 7 adalah 30, dan 30 < 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 8, dan nilai tertinggi = 14

jadi 8 + 14 =22, lalu 22/2 =11

3. karena nomer urut 11 adalah 47, dan 47 > 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 8, dan nilai tertinggi = 10

jadi 8 + 10 =18, lalu 18/2 =9

4. karena nomer urut 9 adalah 41, dan 41 < 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 10, dan nilai tertinggi = 10

jadi 10 + 10 =20, lalu 20/2 =10

nomer 10 adalah kunci dari nomer 42, dimana kunci 42 = 42, ketemu

Program mencari data pada Array menggunakan sequential Search

Program mencari data pada Array menggunakan sequential Search
import java.io.*;
class tugasModul6
{
public static void main (String args []) throws Exception
{
int pilih = 0;
BufferedReader inputan = new BufferedReader (new InputStreamReader(System.in));
String [][] data = new String [100][100];
String ulang = “”;
while (true)
{
System.out.println(”\tMENU”);
System.out.print(”=====================\n”);
System.out.println(”1. Input Data”);
System.out.println(”2. Pencarian Data”);
System.out.println(”3. Keluar”);
System.out.print(”=====================\n”);
System.out.print(”Masukkan Pilihan Anda :”);
pilih = Integer.parseInt(inputan.readLine());
switch (pilih)
{
case 3 : System.exit(0);
case 1 :
for (int i=0;;i++)
{
System.out.print(”Masukkan Kode Barang : “);
data [i][0] = inputan.readLine();
if (data [i][0].equals(”/”)) break;
else
{
System.out.print(”Masukkan Nama Barang : “);
data [i][1] = inputan.readLine();
System.out.print(”Masukkan Jumlah Barang : “);
data [i][2] = inputan.readLine();
System.out.print(”Masukkan Harga Barang : “);
data [i][3] = inputan.readLine();
System.out.println();
}
}
break;
case 2 :
System.out.print(”Masukkan kode barang yang ingin anda cari: “);
String cari = inputan.readLine();
for (int i=0;i<100;i++)
{
if (cari.equals(data [i][0]))
{
System.out.print(”====================================”);
System.out.print(”Kode Barang\t : “+data[i][0]+”\n”);
System.out.print(”Nama Barang\t : “+data[i][1]+”\n”);
System.out.print(”Jumlah Barang\t : “+data[i][2]+”\n”);
System.out.print(”Harga Barang\t : “+data[i][3]+”\n”);
System.out.print(”====================================”);
break;
}
else System.out.println(”Data Tidak Ditemukan”);
}
break;
default : System.out.print(”Pilihan Tidak Ada /n”);
}
}
}
}

SORTING

Istilah sorting tentu tidak asing di telinga kita, yaitu istilah untuk mengurutkan data. Ada dua bentuk sorting yaitu secara ascending dan descending. Sorting secara ascending adalah cara mengurutkan data mulai data bernilai terkecil sampai terbesar. Sedangkan descending mengurutkan data mulai dari data terbesar sampai terkecil. Sebagai contoh misalkan diberikan data berupa bilangan berikut ini:

3 9 1 4 0 2

Hasil sorting ascending adalah 0 1 2 3 4 9, dan hasil secara descending adalah 9 4 3 2 1 0.

Nah pada artikel kali ini akan dibahas bagaimana kita mencari algoritma untuk melakukan sorting ini sekaligus implementasinya.

OK, misalkan diberikan data sebagaimana data di atas. Bagaimana cara kita mengurutkan data secara ascending? Yup… untuk memudahkan pemrosesan data, lebih enak kalau kita nyatakan terlebih dahulu data bilangan di atas ke dalam bentuk notasi x_i dengan i = 1, 2, …, 6. Sehingga dalam hal ini x₁=3, x₂=9, x₃=1, x₄=4, x₅=0 dan x₆=2.

Nah… selanjutnya apabila kita ingin mengurutkan data secara ascending, maka harapan kita urutan data pertama adalah data yang memiliki nilai paling kecil. Oleh karena itu kita harus mencari data terkecil dari semua data yang ada, lalu tempatkan ia ke data urutan pertama. Lho… lantas, bagaimana dengan data urutan pertama sebelumnya? Bukankah nantinya dia akan tertimpa dengan data terkecil itu? Oh tidak… data urutan pertama sebelumnya akan kita tukar tempatnya dengan milik data terkecil. Misalkan data terkecil terletak pada urutan ke-4 dari seluruh data, maka data pertama kita tempatkan ke urutan ke-4 dan data terkecil diletakkan ke urutan pertama.

Ini dia pseudocode dalam Pascal untuk mencari nilai terkecil dari semua data (x₁, x₂, …, x₆) sekaligus mencari tempatnya.

min := x[1];
for i:=1 to 6 do
begin
   if (x[i] <= min) then
   begin 
      min := x[i];
      tempatnya_min := i;
   end;
end;

Jadi pertama-tama, kita anggap nilai minimum adalah x₁. Lalu nilai minimum ini kita bandingkan dengan semua data yang ada. Jika ditemukan nilai x_i yang lebih kecil atau sama dengan nilai minimum, maka x_i itulah nilai minimum yang baru, sekaligus tempat miliknya data minimum ini (i) kita catat. Nah setelah nilai minimum dari semua data ditemukan, maka selanjutnya kita tukar tempat nilai minimum tadi dengan tempat data pertama.

temp := x[1];
x[1] := x[tempatnya_min];
x[tempatnya_min] := temp;

Sehingga pseudocode proses mencari nilai terkecil dan menukar tempatnya dengan data pertama menjadi

min := x[1];
for i:=1 to 6 do
begin
   if (x[i] <= min) then
   begin 
      min := x[i];
      tempatnya_min := i;
   end;
end;

temp := x[1];
x[1] := x[tempatnya_min];
x[tempatnya_min] := temp;

Nah setelah ditukar tempat antara data pertama dengan data terkecil maka urutan data menjadi

0 9 1 4 3 2

Proses selanjutnya, kita ulangi lagi proses yang sama yaitu mencari data terkecil dari kelompok data urutan ke-2 sampai dengan ke-6. Lalu tukar tempat data terkecil tersebut dengan tempat data urutan ke-2. Berikut ini pseudocodenya

min := x[2];
for i:=2 to 6 do
begin
   if (x[i] <= min) then
   begin 
      min := x[i];
      tempatnya_min := i;
   end;
end;

temp := x[2];
x[2] := x[tempatnya_min];
x[tempatnya_min] := temp;

Tukar tempat antara data minimum dengan data ke-2 menghasilkan urutan data

0 1 9 4 3 2

Proses yang sama kembali dilakukan untuk kelompok data mulai urutan ke-3 sampai ke-6. Cari nilai minimumnya, lalu tukar tempat dengan data ke-3. Begitu seterusnya sampai dengan kelompok data ke-6 sampai ke-6. Berikut ini hasil urutan data untuk setiap proses

hasil urutan untuk kelompok data x₃ s/d x₆ : 0 1 2 4 3 9
hasil urutan untuk kelompok data x₄ s/d x₆ : 0 1 2 3 4 9
hasil urutan untuk kelompok data x₅ s/d x₆ : 0 1 2 3 4 9
hasil urutan untuk kelompok data x₆ s/d x₆ : 0 1 2 3 4 9

Nah… setelah proses selesai diperolehlah data yang terurut secara ascending. Pada contoh ini sebenarnya proses sorting ascending selesai pada kelompok data x₄ s/d x₆. Namun untuk keperluan generalisasi (bisa diterapkan ke semua kasus) maka kita selesaikan proses sampai dengan kelompok data terakhir.

Dengan demikian secara umum, untuk data x₁ … x_n, berikut ini pseudocode untuk sorting secara ascending

for kelompok := 1 to n do
begin
  min := x[kelompok];
  for i := kelompok to n do
  begin
     if (x[i] <= min) then
     begin 
        min := x[i];
        tempatnya_min := i;
     end;
  end;

  temp := x[kelompok];
  x[kelompok] := x[tempatnya_min];
  x[tempatnya_min] := temp;
end;

Sedangkan berikut ini contoh implementasi algoritma sorting ascending di atas pada kasus yang diberikan di atas.

program sorting;
var x : array[1..100] of integer;
   i, n, min, kelompok, temp, tempatnya_min : integer;
begin
   { membuat data array yang terdiri dari data : 3 9 1 4 0 2 }

   x[1] := 3;
   x[2] := 9;
   x[3] := 1;
   x[4] := 4;
   x[5] := 0;
   x[6] := 2;

   n := 6; {jumlah data}

   { proses sorting ascending }

   for kelompok := 1 to n do
   begin
      min := x[kelompok];
      for i := kelompok to n do
      begin
         if (x[i] <= min) then
         begin
            min := x[i];
            tempatnya_min := i;
         end;
      end;

      temp := x[kelompok];
      x[kelompok] := x[tempatnya_min];
      x[tempatnya_min] := temp;
   end;

   { menampilkan hasil sorting }

   for i:=1 to n do
   begin
      writeln(x[i], ' ');
   end;
end.

Lantas bagaimana dengan sorting descending? Ya… berarti kita tidak lagi mencari data minimum, tapi data maksimum. Bagaimana caranya? ya… tinggal ubah saja tanda <= menjadi >=. Oya, jangan lupa ubah pula nama variabel min menjadi max karena nantinya menjadi lucu, wong mencari nilai maksimum kok nama variabelnya ‘min’, meskipun gak pengaruh di output.

Oya… Satu lagi, algoritma di atas bukan satu-satunya untuk melakukan sorting. Silakan Anda cari algoritma sorting yang lain ya…

OK… mudah-mudahan artikel ini ada manfaatnya.

linked list

Linked list

Linked List atau senarai berantai adalah kumpulan atau koleksi dari komponen yang dinamakan node. Setiap node menyimpan informasi tentang alamat dari node berikutnya (Malik, 2003). Sebuah node terdiri dari dua bagian, yaitu data dan link.

Apabila kita menggunakan java, konsep linked list ini sudah terlingkupi dalam Java Collection Framework (JCF). Dengan Java, kita tidak perlu lagi membuat LinkedList. Kita tinggal menggunakan class yang sudah disediakan dalam JCF.

Berikut syntax yang anda tuliskan kalau anda menggunakan JCF:

import java.util.*;

public class MyLinkedList {

public static void main(String[] args) {

LinkedList list = new LinkedList();

list.add(5);

list.addFirst(3);

list.addLast(9);

Iterator it = list.iterator();

while (it.hasNext()) {

System.out.println(”angka: ” + it.next());

}

}

}

Dalam contoh berikut, linked list akan dimanfaatkan untuk mencatat nomor telepon. Untuk itu, dibuat class untuk menampung data dari tiap orang, yaitu dalam class PhoneBook.

import java.util.*;

public class CobaLinkedList {

public static void main(String[] args) {

LinkedList list = new LinkedList();

list.add(new PhoneBook(”Arwan”,”0812157826″));

list.add(new PhoneBook(”Roni”,”Ra duwe”));

list.addFirst(new PhoneBook(”Hari”,”0892392929″));

list.addLast(new PhoneBook(”Edi”,”0839298493″));

list.remove(1);

Iterator it = list.iterator();

while (it.hasNext()) {

PhoneBook tampil = (PhoneBook) it.next();

System.out.println(”nama: ” + tampil.nama);

System.out.println(”No HP: ” + tampil.noHP);

}

}

}

class PhoneBook {

String nama;

String noHP;

public PhoneBook(String nama, String noHP) {

this.nama = nama;

this.noHP = noHP;

}

}

Dalam contoh di atas, kita memanfaatkan LinkedList yang sudah ada dalam Java Collection Framework. Beriikut kalau anda ingin membuat class linked list sendiri, berikut class listnya:

public class MyList {

Object elemen;

MyList next;

public MyList(Object elemen) {

this.elemen = elemen;

this.next = null;

}

}

Untuk menambahkan list di depan, terlebih dahulu anda harus menghubungkan list yang baru dngan list yang sudah ada, kemudian memindahkan ujung depan dari list menjadi list yang baru anda masukkan. Berikut syntax untuk tambah depan:

public static MyList tambahDepan(MyList list, Object elemen) {

MyList temp = new MyList(elemen);

temp.next = list;

return temp;

}

Untuk menambahkan di belakang, maka terlebih dahulu anda harus mencari list yang paling belakang, kemudian mengarahkan list paling belakang ke dalam list yang baru anda masukkan. Berikut syntax untuk tambah belakang:

public static MyList tambahBelakang(MyList list, Object elemen) {

MyList temp = new MyList(elemen);

MyList depan = list;

while (list.next != null) {

list = list.next;

}

// sudah di akhir

list.next = temp;

return depan;

}

Untuk menambahkan di tengah, ini yang agak harus hati-hati. Jangan sampai anda menghilangkan link ke list berikutnya. Utuk itu anda harus mencari posisi yang tepat, kemudian mengarahkan link list baru anda dengan list setelah list, baru kemudian mengarahkan link dari list ke list baru anda. Berikut syntax untuk tambah tengah:

public static MyList tambahTengah(MyList list, Object elemen, int index) {

MyList temp = new MyList(elemen);

MyList depan = list;

int i=0;

while ((list.next != null) && (i < (index-1))) {

i++;

list = list.next;

}

temp.next = list.next;

list.next = temp;

return depan;

}

Dikutip dari: arwankhoiruddin.staff.uii.ac.id/2009/03/25/linked-list/

tanpa pengubahan…