ORGANISASI BERKAS - BERKAS SEKUENSIAL
Organisasi Berkas
- Dalam menggorganisasi berkas secara Sekuensial, Langsung,
maupun Sekuensial Berindeks memiliki cara yang berbeda
dalam penyusunan rekaman-rekaman yang membentuk
berkas / file tersebut.
- Rekaman-rekaman data tersebut tersusun atas sejumlah
medan Data.
- Medan Data : Nilai Dasar yang membentuk sebuah rekaman
Data
- Rekaman Data : Koleksi Berbagai Medan yang berisi
beberapa item data elementer
- Berkas Data : koleksi dari rekaman-rekaman yang sama,
yang diletakan dalam peralatan penyimpanan data
komputer
Pencarian Berkas Secara Sekuensial
- Pencarian berkas secara sekuensial dilakukan dengan
memproses rekaman-rekaman dalam berkas sesuai dengan
urutan keberadaan rekaman-rekaman tersebut sampai
ditemukan rekaman-rekaman yang diinginkan atau semua
rekaman akan terbaca.
Pencarian Biner (Binary Search)
- Untuk sebuah berkas yang sudah di urutkan, jumlah
probe yang diperlukan untuk membaca sejumlah
rekaman dapat di usahakan untuk diperkecil lagi
dengan menggunakan teknik pencarian biner.
- Jika Kuncicari < Kuncitengah, maka bagian berkas mulai
dari Kuncitengah sampai akhir berkas dielaminiansi.
Contoh 1
- Cari rekaman dengan kunci 49 .... ?
1 2 3 4 5 6 7 8 9
- Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]
- Iterasi 2 : 21, 25, 28, 33, 38, [39, 48, 49, 69]
- Iterasi 3 : 21, 25, 28, 33, 38, 39, 48, [49, 69]
Perhitungan :
- Iterasi 1 : TENGAH1 = [1+9)/2] = 5
Kuncicari : Kuncitengah -> 49 > 38
-> AWAL = TENGAH1 + 1 = 5+1 = 6
1 2 3 4 5 6 7 8 9
Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]
- Iterasi 2 : TENGAH2 = [6+9)/2] = 7
Kuncicari : Kuncitengah -> 49 > 48
-> AWAL = TENGAH2 + 1 = 7+1 = 8
1 2 3 4 5 6 7 8 9
Iterasi 2 : 21, 25, 28, 33, 38, [39, 48, 49, 69]
- Iterasi 3 : TENGAH3 = [8+9)/2] = 8
Kuncicari : Kuncitengah -> 49 = 49
-> Ketemu, Probe = 3
1 2 3 4 5 6 7 8 9
Iterasi 3 : 21, 25, 28, 33, 38, 39, 48, [49, 69]
Contoh 2
- Cari rekaman dengan kunci 27 .... ?
1 2 3 4 5 6 7 8 9
- Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]
- Iterasi 2 : [21, 25, 28, 33], 38, 39, 48, 49, 69
- Iterasi 3 : 21, 25, [28, 33], 38, 39, 48, 49, 69
- Iterasi 4 : 21, 25], [28, 33, 38, 39, 48, 49, 69
Perhitungan :
- Iterasi 1 : TENGAH1 = [(1+9)/2] = 5
Kuncicari : Kuncitengah -> 27 < 38
-> AKHIR = TENGAH1 - 1 = 5-1 = 4
1 2 3 4 5 6 7 8 9
Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]
- Iterasi 2 : TENGAH2 = [1+4)/2] = 2
Kuncicari : Kuncitengah -> 27 > 25
-> AWAL = TENGAH2 + 1 = 2+1 = 3
1 2 3 4 5 6 7 8 9
Iterasi 2 : [21, 25, 28, 33], 38, 39, 48, 49, 69
- Iterasi 3 : TENGAH3 = [3+4)/2] = 3
Kuncicari : Kuncitengah -> 27 < 28
-> AKHIR = TENGAH3 - 1 = 3-1 = 2
1 2 3 4 5 6 7 8 9
Iterasi 3 : 21, 25, [28, 33], 38, 39, 48, 49, 69
- Iterasi 4 : AWAL > AKHIR -> Rekaman Tidak ditemukan
1 2 3 4 5 6 7 8 9
Iterasi 4 : 21, 25], [28, 33, 38, 39, 48, 49, 69
Pencarian Interpolasi
- Pencarian Interpolasi menentukan posisi yang akan
diperbandingkan berikutnya berdasarkan posisi yang
diestimasi dari sisa rekaman yang belum diperiksa.
- Syarat dalam pencarian berkas dalam pencarian interpolasi
adalah kunci rekaman adalah bilangan numeris, karena
dalam proses pencarian interpolasi posisi rekaman yang
akan dibandingkan dihitung dengan melibatkan proses
aritmatik tehadap kunci awal, kunci akhir, dan kunci yang
di cari.
- Kunci awal adalah kunci awal pada posisi pencarian
terakhir, bukan kunci awal berkas.
CONTOH 1
- Untuk rekaman dengan susunan sebagai berikut :
1 2 3 4 5 6 7 8 9
[21, 25, 28, 33, 38, 39, 48, 49, 69]
Berapa probe untuk menentukan rekaman dengan kunci 49 bila
menggunakan pencarian interpolasi ?
1 2 3 4 5 6 7 8 9
- Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]
- Iterasi 2 : 21, 25, 28, 33, 38, 39, [48, 49, 69]
Perhitungan
- Iterasi 1 Berikut1 = 1 + 49-21/69-2 (9 − 1) = 5.66666 ≈ 5
-> Kcari ? Kberikut = 49 > 38, Maka AWAL = Berikut1 + 1 = 5+1 =6
1 2 3 4 5 6 7 8 9
Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]
- Iterasi 2 Berikut2 = 6 + 49-39/69-39 (9 − 6) = 7
-> Kcari ? Kberikut = 49 > 48, Maka AWAL = Berikut2 + 1 = 7+1 =8
1 2 3 4 5 6 7 8 9
Iterasi 2 : 21, 25, 28, 33, 38, [39, 48, 49, 69]
- Iterasi 3 Berikut3 = 8 + 49-49/69-4 (9 − 7) = 8
-> Kcari ? Kberikut = 49 = 49, Maka Ketemu, Probe = 3
1 2 3 4 5 6 7 8 9
Iterasi 3 : 21, 25, 28, 33, 38, 39, 48, [49, 69]