# ==========================================
# LATIHAN 12
# BINARY SEARCH
# ==========================================
validasi_pencarian <- function(x, target, urut = FALSE) {
if (!is.numeric(x) || length(dim(x)) > 1L ||
anyNA(x) || any(!is.finite(x))) {
stop("x harus larik numerik satu dimensi tanpa NA atau Inf")
}
if (!is.numeric(target) || length(target) != 1L ||
!is.finite(target)) {
stop("target harus satu angka berhingga")
}
if (urut && is.unsorted(x, strictly = FALSE)) {
stop("Data harus terurut menaik")
}
invisible(TRUE)
}
# ------------------------------------------
# FUNGSI BINARY BOOLEAN
# ------------------------------------------
bin_boolean <- function(x, target) {
validasi_pencarian(x, target, urut = TRUE)
kiri <- 1L
kanan <- length(x)
ketemu <- FALSE
posisi <- NA_integer_
while (kiri <= kanan && !ketemu) {
tengah <- kiri + (kanan - kiri) %/% 2
if (x[tengah] == target) {
ketemu <- TRUE
posisi <- tengah
} else if (x[tengah] < target) {
kiri <- tengah + 1L
} else {
kanan <- tengah - 1L
}
}
posisi
}
# ------------------------------------------
# FUNGSI BINARY TANPA BOOLEAN
# ------------------------------------------
bin_tanpa_boolean <- function(x, target) {
validasi_pencarian(x, target, urut = TRUE)
kiri <- 1L
kanan <- length(x)
while (kiri <= kanan) {
tengah <- kiri + (kanan - kiri) %/% 2
if (x[tengah] == target) return(tengah)
if (x[tengah] < target) {
kiri <- tengah + 1L
} else {
kanan <- tengah - 1L
}
}
NA_integer_
}
# ------------------------------------------
# FUNGSI BINARY POSISI PERTAMA
# ------------------------------------------
bin_pertama <- function(x, target) {
validasi_pencarian(x, target, urut = TRUE)
kiri <- 1L
kanan <- length(x)
posisi <- NA_integer_
while (kiri <= kanan) {
tengah <- kiri + (kanan - kiri) %/% 2
if (x[tengah] >= target) {
if (x[tengah] == target) {
posisi <- tengah
}
kanan <- tengah - 1L
} else {
kiri <- tengah + 1L
}
}
posisi
}
# ------------------------------------------
# FUNGSI JEJAK BINARY SEARCH
# ------------------------------------------
jejak_binary <- function(x, target) {
validasi_pencarian(x, target, urut = TRUE)
kiri <- 1L
kanan <- length(x)
jejak <- data.frame(
langkah = integer(),
kiri = double(),
kanan = double(),
tengah = double(),
nilai = double(),
keputusan = character()
)
while (kiri <= kanan) {
tengah <- kiri + (kanan - kiri) %/% 2
keputusan <- if (x[tengah] == target) {
"Ditemukan"
} else if (x[tengah] < target) {
"Cari kanan"
} else {
"Cari kiri"
}
jejak <- rbind(jejak, data.frame(
langkah = nrow(jejak) + 1L,
kiri = kiri,
kanan = kanan,
tengah = tengah,
nilai = x[tengah],
keputusan = keputusan
))
if (x[tengah] == target) break
if (x[tengah] < target) {
kiri <- tengah + 1L
} else {
kanan <- tengah - 1L
}
}
jejak
}
# ------------------------------------------
# FUNGSI MENGHITUNG KUNJUNGAN SEQUENTIAL
# ------------------------------------------
kunjungan_sequential <- function(x, target) {
validasi_pencarian(x, target)
banyak <- 0L
for (i in seq_along(x)) {
banyak <- banyak + 1L
if (x[i] == target) break
}
banyak
}
# ==========================================
# PEMBAHASAN LATIHAN PERTEMUAN 12
# ==========================================
# ------------------------------------------
# 12A. JEJAK BINARY SEARCH
# ------------------------------------------
cat("\n=== LATIHAN 12A ===\n")
##
## === LATIHAN 12A ===
lat_urut <- seq(10, 100, by = 10)
print(jejak_binary(lat_urut, 80))
## langkah kiri kanan tengah nilai keputusan
## 1 1 1 10 5 50 Cari kanan
## 2 2 6 10 8 80 Ditemukan
# ------------------------------------------
# 12B. DUA VARIAN BINARY SEARCH
# ------------------------------------------
cat("\n=== LATIHAN 12B ===\n")
##
## === LATIHAN 12B ===
for (target in c(10, 100, 105)) {
cat("\nTarget:", target, "\n")
cat("Binary Boolean:\n")
print(bin_boolean(lat_urut, target))
cat("Binary Tanpa Boolean:\n")
print(bin_tanpa_boolean(lat_urut, target))
}
##
## Target: 10
## Binary Boolean:
## [1] 1
## Binary Tanpa Boolean:
## [1] 1
##
## Target: 100
## Binary Boolean:
## [1] 10
## Binary Tanpa Boolean:
## [1] 10
##
## Target: 105
## Binary Boolean:
## [1] NA
## Binary Tanpa Boolean:
## [1] NA
# ------------------------------------------
# 12C. BINARY SEARCH PADA DATA DUPLIKAT
# ------------------------------------------
cat("\n=== LATIHAN 12C ===\n")
##
## === LATIHAN 12C ===
data_ganda <- c(10, 20, 20, 20, 30)
print(c(
binary_dasar = bin_boolean(data_ganda, 20),
binary_pertama = bin_pertama(data_ganda, 20)
))
## binary_dasar binary_pertama
## 3 2
# ------------------------------------------
# 12D. PENCARIAN KODE PRODUK 103
# ------------------------------------------
cat("\n=== LATIHAN 12D ===\n")
##
## === LATIHAN 12D ===
# Data produk simulasi sesuai materi
produk <- data.frame(
kode = c(104, 101, 107, 103, 106, 102, 105),
nama = c("Telur", "Beras", "Kopi", "Minyak",
"Garam", "Gula", "Tepung"),
stok = c(25, 40, 18, 30, 50, 35, 28)
)
# Mengurutkan produk dan menyimpan pemetaan baris asli
urutan <- order(produk$kode)
produk_urut <- produk[urutan, , drop = FALSE]
# Mencari kode 103
p <- bin_tanpa_boolean(produk_urut$kode, 103)
if (!is.na(p)) {
cat("Posisi terurut dan baris asli:\n")
print(c(
posisi_terurut = p,
baris_asli = urutan[p]
))
cat("Informasi produk:\n")
print(produk_urut[p, , drop = FALSE])
}
## Posisi terurut dan baris asli:
## posisi_terurut baris_asli
## 3 4
## Informasi produk:
## kode nama stok
## 4 103 Minyak 30
# ------------------------------------------
# 12E. VALIDASI DATA TIDAK TERURUT
# ------------------------------------------
cat("\n=== LATIHAN 12E ===\n")
##
## === LATIHAN 12E ===
print(
tryCatch(
bin_boolean(c(30, 10, 20), 20),
error = function(e) conditionMessage(e)
)
)
## [1] "Data harus terurut menaik"
# ------------------------------------------
# 12F. PERBANDINGAN KUNJUNGAN
# ------------------------------------------
cat("\n=== LATIHAN 12F ===\n")
##
## === LATIHAN 12F ===
data_besar <- seq_len(1024)
target_uji <- 1024
print(c(
sequential = kunjungan_sequential(data_besar, target_uji),
binary = nrow(jejak_binary(data_besar, target_uji))
))
## sequential binary
## 1024 11
# ==========================================
# SELESAI LATIHAN 12
# ==========================================