Untuk sebuah berkas dengan rekaman yang sudah diurutkan, jumlah probe yang diperlukan untuk membaca sebuah rekaman dapat diusahakan untuk diperkecil dengan menggunakan teknik pencarian biner. Jika Kunci Kunci maka bagian berkas mulai dari Kunci sampai akhir berkas dieliminasi. Sebaliknya jika Kunci Kunci maka bagian berkas mulai dari depan sampai dengan Kunci-tengah dieliminasi. Dengan mengulang proses pembandingan terhadap rekaman tengah, maka lokasi rekaman yang diinginkan akan ditemukan atau diketahui bahwa rekaman yang diinginkan tersebut tidak berada dalam berkas.
Program Pascal untuk Binary Search (pencarian biner) bekerja dengan membagi dua array terurut secara berulang untuk menemukan nilai target. Metode ini efisien dengan kompleksitas waktu, di mana posisi tengah dibandingkan dengan target, dan ruang pencarian dipersempit ke kiri atau kanan hingga ditemukan.
Berikut adalah contoh kode program Pascal untuk algoritma pencarian biner:
Pascal (Iteratif)
program BinarySearch;
uses crt;
{ Mendefinisikan tipe data array }
type
IntArray = array[1..100] of integer;
{ Fungsi Binary Search }
function BSearch(var arr: IntArray; n, target: integer): integer;
var
low, high, mid: integer;
begin
low := 1;
high := n;
BSearch := 0; { Default 0 jika tidak ditemukan }
while (low <= high) do
begin
mid := (low + high) div 2;
if (arr[mid] = target) then
begin
BSearch := mid; { Target ditemukan }
exit;
end
else if (arr[mid] < target) then
low := mid + 1 { Cari di kanan }
else
high := mid - 1; { Cari di kiri }
end;
end;
{ Program Utama }
var
data: IntArray;
n, i, target, hasil: integer;
begin
clrscr;
write('Masukkan jumlah elemen: ');
readln(n);
{ Input data (harus terurut) }
writeln('Masukkan ', n, ' elemen terurut (ascending):');
for i := 1 to n do
begin
write('Elemen ', i, ': ');
readln(data[i]);
end;
write('Masukkan nilai yang dicari: ');
readln(target);
{ Panggil fungsi }
hasil := BSearch(data, n, target);
{ Output hasil }
if (hasil <> 0) then
writeln('Nilai ', target, ' ditemukan pada indeks: ', hasil)
else
writeln('Nilai ', target, ' tidak ditemukan.');
readkey;
end.
Algoritma Pencarian Biner yang lengkap diperlihatkan pada Algoritma 3.1 berikut ini.
Proc pencarian_biner
/* n buah rekaman dalam berkas diurutkan menaik menurut kunci rekaman */
1 AWAL:= 1
2 Akhir:= n
3 while AWAL ≤ AKHIR do
13 end
tengah:L(AWAL+AKHIR) / 2」
if kunci (cari) kunci (tengah) pencarian berakhir.
else if kunci (cari) > kunci (tengah)
AWAL TENGAH + 1
else
AKHIR: TENGAH-1
11 rekaman tidak ditemukan
end pencarian biner
Algoritma 3.1 Pencarian biner
Keterangan X menunjukkan integer X atau pembulatan terhadap X.
Python (Iteratif)
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
# Cek jika target ada di tengah
if arr[mid] == target:
return mid
# Jika target lebih besar, abaikan separuh kiri
elif arr[mid] < target:
left = mid + 1
# Jika target lebih kecil, abaikan separuh kanan
else:
right = mid - 1
# Target tidak ditemukan
return -1
# Contoh Penggunaan
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(data, target)
print(f"Elemen ditemukan pada indeks: {result}") # Output: 5
C++
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, 0, n - 1, target);
cout << "Elemen ditemukan pada indeks: " << result << endl; // Output: 5
return 0;
}
Algoritma Pencarian Biner membandingkan Key rekaman yang dicari dengan kunci rekaman pada posisi tengah dari berkas. Bila sama (kasus 1) berarti rekaman yang diinginkan sudah ditemukan, atau kalau tidak sama (kasus 2) berarti separuh dari rekaman-rekaman dalam berkas akan dieliminasi dari perbandingan yang selanjutnya. Bila yang terjadi adalah kasus 2 maka proses pembandingan terhadap rekaman pada posisi di tengah dilanjutkan menggunakan rekaman rekaman yang tersisa.
Tidak ada komentar:
Posting Komentar