# ==========================================
# PEMBAHASAN ENAM LATIHAN PERTEMUAN 11
# PENCARIAN SEKUENSIAL (SEQUENTIAL SEARCH)
# ==========================================
# 1. Membuat fungsi Sequential Boolean
seq_boolean <- function(x, target) {
if (any(is.na(x))) {
stop("Data tidak sah: terdapat NA")
}
for (i in seq_along(x)) {
if (x[i] == target) {
return(i)
}
}
return(-1)
}
# 2. Membuat fungsi Sequential Tanpa Boolean
seq_tanpa_boolean <- function(x, target) {
if (any(is.na(x))) {
stop("Data tidak sah: terdapat NA")
}
i <- 1
while (i <= length(x) && x[i] != target) {
i <- i + 1
}
if (i <= length(x)) {
return(i)
} else {
return(-1)
}
}
# 3. Membuat fungsi Sequential Terurut
seq_terurut <- function(x, target) {
if (any(is.na(x))) {
stop("Data tidak sah: terdapat NA")
}
for (i in seq_along(x)) {
if (x[i] == target) {
return(i)
}
if (x[i] > target) {
break
}
}
return(-1)
}
# 4. Membuat fungsi Sequential Sentinel
seq_sentinel <- function(x, target) {
if (any(is.na(x))) {
stop("Data tidak sah: terdapat NA")
}
n <- length(x)
data_asli <- x
x <- c(x, target)
i <- 1
while (x[i] != target) {
i <- i + 1
}
if (i <= n) {
return(i)
} else {
return(-1)
}
}
# ==========================================
# PEMBAHASAN ENAM LATIHAN
# ==========================================
lat_x <- c(12, 7, 19, 7, 25)
# 11A Sequential Boolean posisi pertama 7
cat("\n11A Sequential Boolean\n")
##
## 11A Sequential Boolean
print(seq_boolean(lat_x, 7))
## [1] 2
# 11B Tanpa Boolean target tidak ada dan larik kosong
cat("\n11B Sequential Tanpa Boolean\n")
##
## 11B Sequential Tanpa Boolean
print(seq_tanpa_boolean(lat_x, 8))
## [1] -1
print(seq_tanpa_boolean(numeric(), 8))
## [1] -1
# 11C Terurut berhenti ketika nilai melebihi target
cat("\n11C Sequential Terurut\n")
##
## 11C Sequential Terurut
print(seq_terurut(c(5, 10, 15, 20, 25), 12))
## [1] -1
# 11D Sentinel dan keutuhan data asli
cat("\n11D Sequential Sentinel\n")
##
## 11D Sequential Sentinel
lat_awal <- lat_x
print(seq_sentinel(lat_x, 99))
## [1] -1
print(identical(lat_x, lat_awal))
## [1] TRUE
# 11E Posisi pertama berbeda dengan semua posisi
cat("\n11E Perbandingan Match dan Which\n")
##
## 11E Perbandingan Match dan Which
print(match(7, lat_x))
## [1] 2
print(which(lat_x == 7))
## [1] 2 4
# 11F Data tidak sah ditolak dan pesan ditangkap
cat("\n11F Penanganan Data Tidak Sah\n")
##
## 11F Penanganan Data Tidak Sah
print(
tryCatch(
seq_boolean(c(12, NA, 19), 19),
error = function(e) conditionMessage(e)
)
)
## [1] "Data tidak sah: terdapat NA"
# ==========================================
# PEMBAHASAN ENAM LATIHAN PERTEMUAN 12
# BINARY SEARCH (PENCARIAN BINER)
# ==========================================
# 1. Fungsi validasi data terurut
validasi_urut <- function(x) {
if (!is.numeric(x)) {
stop("Data harus berupa numerik")
}
if (anyNA(x)) {
stop("Data tidak sah: terdapat NA")
}
if (length(x) > 1 && any(diff(x) < 0)) {
stop("Data harus terurut menaik")
}
return(TRUE)
}
# 2. Fungsi jejak Binary Search
jejak_binary <- function(x, target) {
validasi_urut(x)
kiri <- 1
kanan <- length(x)
langkah <- data.frame(
langkah = integer(),
kiri = integer(),
kanan = integer(),
tengah = integer(),
nilai = numeric()
)
nomor <- 0
while (kiri <= kanan) {
tengah <- floor((kiri + kanan) / 2)
nomor <- nomor + 1
langkah <- rbind(
langkah,
data.frame(
langkah = nomor,
kiri = kiri,
kanan = kanan,
tengah = tengah,
nilai = x[tengah]
)
)
if (x[tengah] == target) {
break
} else if (x[tengah] < target) {
kiri <- tengah + 1
} else {
kanan <- tengah - 1
}
}
return(langkah)
}
# 3. Fungsi Binary Search dengan Boolean
bin_boolean <- function(x, target) {
validasi_urut(x)
kiri <- 1
kanan <- length(x)
while (kiri <= kanan) {
tengah <- floor((kiri + kanan) / 2)
if (x[tengah] == target) {
return(tengah)
} else if (x[tengah] < target) {
kiri <- tengah + 1
} else {
kanan <- tengah - 1
}
}
return(-1)
}
# 4. Fungsi Binary Search tanpa Boolean
bin_tanpa_boolean <- function(x, target) {
validasi_urut(x)
kiri <- 1
kanan <- length(x)
posisi <- -1
repeat {
if (kiri > kanan) {
break
}
tengah <- floor((kiri + kanan) / 2)
if (x[tengah] == target) {
posisi <- tengah
break
}
if (x[tengah] < target) {
kiri <- tengah + 1
} else {
kanan <- tengah - 1
}
}
return(posisi)
}
# 5. Fungsi mencari posisi pertama pada data duplikat
bin_pertama <- function(x, target) {
validasi_urut(x)
kiri <- 1
kanan <- length(x)
posisi <- -1
while (kiri <= kanan) {
tengah <- floor((kiri + kanan) / 2)
if (x[tengah] == target) {
posisi <- tengah
kanan <- tengah - 1
} else if (x[tengah] < target) {
kiri <- tengah + 1
} else {
kanan <- tengah - 1
}
}
return(posisi)
}
# 6. Fungsi menghitung kunjungan Sequential Search
kunjungan_sequential <- function(x, target) {
for (i in seq_along(x)) {
if (x[i] == target) {
return(i)
}
}
return(length(x))
}
# ==========================================
# MENYIAPKAN DATA LATIHAN
# ==========================================
lat_urut <- seq(10, 100, by = 10)
# ==========================================
# 12A JEJAK PENCARIAN 80
# ==========================================
cat("\n12A Jejak Binary Search\n")
##
## 12A Jejak Binary Search
print(jejak_binary(lat_urut, 80))
## langkah kiri kanan tengah nilai
## 1 1 1 10 5 50
## 2 2 6 10 8 80
# ==========================================
# 12B KASUS BATAS KEDUA VARIAN BINARY
# ==========================================
cat("\n12B Kasus Batas Binary Search\n")
##
## 12B Kasus Batas Binary Search
print(bin_boolean(lat_urut, 10))
## [1] 1
print(bin_tanpa_boolean(lat_urut, 100))
## [1] 10
print(bin_boolean(lat_urut, 105))
## [1] -1
# ==========================================
# 12C DUPLIKASI DAN POSISI PERTAMA
# ==========================================
cat("\n12C Pencarian Data Duplikat\n")
##
## 12C Pencarian Data Duplikat
print(bin_boolean(c(10, 20, 20, 20, 30), 20))
## [1] 3
print(bin_pertama(c(10, 20, 20, 20, 30), 20))
## [1] 2
# ==========================================
# 12D KODE 103 PADA TABEL PRODUK
# ==========================================
cat("\n12D Pencarian Kode Produk\n")
##
## 12D Pencarian Kode Produk
# Membuat data produk asli
produk <- data.frame(
kode = c(105, 101, 103, 102, 104),
nama = c("Produk E", "Produk A", "Produk C",
"Produk B", "Produk D"),
harga = c(50000, 10000, 30000, 20000, 40000)
)
# Menyimpan urutan baris asli
urutan <- order(produk$kode)
# Mengurutkan tabel produk berdasarkan kode
produk_urut <- produk[urutan, ]
# Mencari kode produk 103
p <- bin_tanpa_boolean(produk_urut$kode, 103)
if (p != -1) {
print(c(
posisi_terurut = p,
baris_asli = urutan[p]
))
print(produk_urut[p, , drop = FALSE])
} else {
print("Kode produk tidak ditemukan")
}
## posisi_terurut baris_asli
## 3 3
## kode nama harga
## 3 103 Produk C 30000
# ==========================================
# 12E VALIDASI DATA BELUM TERURUT
# ==========================================
cat("\n12E Validasi Data Tidak Terurut\n")
##
## 12E Validasi Data Tidak Terurut
print(
tryCatch(
bin_boolean(c(30, 10, 20), 20),
error = function(e) conditionMessage(e)
)
)
## [1] "Data harus terurut menaik"
# ==========================================
# 12F PERBANDINGAN KUNJUNGAN TARGET TERAKHIR
# ==========================================
cat("\n12F Perbandingan Sequential dan Binary\n")
##
## 12F Perbandingan Sequential dan Binary
print(
c(
sequential = kunjungan_sequential(seq_len(1024), 1024),
binary = nrow(jejak_binary(seq_len(1024), 1024))
)
)
## sequential binary
## 1024 11