# Persiapan Kontrak masukan pencarian ----
# Kode numerik berhingga; pencocokan persis, tanpa NA.
# Vektor bernama dan array 1-D diterima; matriks ditolak.
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)
}
data_acak <- c(31, 17, 42, 9, 25)
data_urut <- c(9, 17, 25, 31, 42)
print(data_acak)
## [1] 31 17 42 9 25
print(data_urut)
## [1] 9 17 25 31 42
# Sequential search dengan variabel Boolean ----
seq_boolean <- function(x, target) {
validasi_pencarian(x, target)
i <- 1L
n <- length(x)
ketemu <- FALSE
while (i <= n && !ketemu) {
if (x[i] == target) {
ketemu <- TRUE
} else {
i <- i + 1L
}
}
if (ketemu) return(i)
NA_integer_
}
print(seq_boolean(data_acak, 9))
## [1] 4
print(seq_boolean(data_acak, 99))
## [1] NA
# Sequential search tanpa variabel Boolean ----
seq_tanpa_boolean <- function(x, target) {
validasi_pencarian(x, target)
for (i in seq_along(x)) {
if (x[i] == target) return(i)
}
NA_integer_
}
print(seq_tanpa_boolean(data_acak, 9))
## [1] 4
print(seq_tanpa_boolean(numeric(), 9))
## [1] NA
# Sequential search pada larik terurut menaik ----
seq_terurut <- function(x, target) {
validasi_pencarian(x, target, urut = TRUE)
i <- 1L
n <- length(x)
while (i <= n && x[i] < target) {
i <- i + 1L
}
if (i <= n && x[i] == target) return(i)
NA_integer_
}
print(seq_terurut(data_urut, 25))
## [1] 3
print(seq_terurut(data_urut, 20))
## [1] NA
# Sequential search dengan sentinel pada salinan lokal ----
seq_sentinel <- function(x, target) {
validasi_pencarian(x, target)
n <- length(x)
kerja <- c(x, target)
i <- 1L
while (kerja[i] != target) {
i <- i + 1L
}
if (i <= n) return(i)
NA_integer_
}
salinan_awal <- data_acak
print(seq_sentinel(data_acak, 9))
## [1] 4
print(seq_sentinel(data_acak, 99))
## [1] NA
print(identical(data_acak, salinan_awal))
## [1] TRUE
print(seq_sentinel(numeric(), 99))
## [1] NA
# Binary search dengan variabel 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
}
contoh_binary <- seq(5, 40, by = 5)
print(bin_boolean(contoh_binary, 35))
## [1] 7
print(bin_boolean(contoh_binary, 34))
## [1] NA
# Binary search tanpa variabel 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_
}
print(bin_tanpa_boolean(contoh_binary, 35))
## [1] 7
print(bin_tanpa_boolean(contoh_binary, 34))
## [1] NA
# Jejak interval 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
}
print(jejak_binary(contoh_binary, 35))
## langkah kiri kanan tengah nilai keputusan
## 1 1 1 8 4 20 Cari kanan
## 2 2 5 8 6 30 Cari kanan
## 3 3 7 8 7 35 Ditemukan
print(jejak_binary(contoh_binary, 34))
## langkah kiri kanan tengah nilai keputusan
## 1 1 1 8 4 20 Cari kanan
## 2 2 5 8 6 30 Cari kanan
## 3 3 7 8 7 35 Cari kiri
# Nilai berulang dan perluasan binary posisi pertama ----
data_ganda <- c(10, 20, 20, 20, 30)
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
}
print(c(sequential = seq_boolean(data_ganda, 20),
binary = bin_boolean(data_ganda, 20),
binary_pertama = bin_pertama(data_ganda, 20)))
## sequential binary binary_pertama
## 2 3 2
print(which(data_ganda == 20))
## [1] 2 3 4
# Studi kasus pencarian kode produk simulasi ----
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)
)
target_kode <- 106
pos_asli <- seq_tanpa_boolean(produk$kode, target_kode)
if (!is.na(pos_asli)) print(produk[pos_asli, , drop = FALSE])
## kode nama stok
## 5 106 Garam 50
urutan <- order(produk$kode)
produk_urut <- produk[urutan, , drop = FALSE]
pos_urut <- bin_tanpa_boolean(produk_urut$kode, target_kode)
if (!is.na(pos_urut)) {
baris_asli <- urutan[pos_urut]
print(c(posisi_terurut = pos_urut, baris_asli = baris_asli))
print(produk_urut[pos_urut, , drop = FALSE])
}
## posisi_terurut baris_asli
## 6 5
## kode nama stok
## 5 106 Garam 50
target_tidak_ada <- bin_boolean(produk_urut$kode, 999)
if (is.na(target_tidak_ada)) print("Kode 999 tidak ditemukan")
## [1] "Kode 999 tidak ditemukan"
print(match(target_kode, produk$kode))
## [1] 5
print(target_kode %in% produk$kode)
## [1] TRUE
print(which(produk$kode == target_kode))
## [1] 5
# Perbandingan kunjungan elemen inti algoritma ----
# Bukan waktu eksekusi dan bukan total biaya validasi.
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
}
data_besar <- seq_len(1024)
target_uji <- c(1, 256, 512, 1024, 2000)
banding <- data.frame(
target = target_uji,
sequential = vapply(target_uji, function(z) {
as.integer(kunjungan_sequential(data_besar, z))
}, integer(1)),
binary = vapply(target_uji, function(z) {
nrow(jejak_binary(data_besar, z))
}, integer(1))
)
print(banding)
## target sequential binary
## 1 1 1 10
## 2 256 256 2
## 3 512 512 1
## 4 1024 1024 11
## 5 2000 1024 11
# Menyimpan keluaran pembelajaran ----
folder_hasil <- tempfile("hasil_searching_R_", tmpdir = getwd())
dir.create(folder_hasil, recursive = TRUE)
write.csv(produk,
file.path(folder_hasil, "data_produk_simulasi.csv"),
row.names = FALSE)
write.csv(jejak_binary(contoh_binary, 35),
file.path(folder_hasil, "jejak_binary_35.csv"), row.names = FALSE)
write.csv(banding,
file.path(folder_hasil, "kunjungan_elemen.csv"), row.names = FALSE)
capture.output(sessionInfo(),
file = file.path(folder_hasil, "sessionInfo.txt"))
cat("Folder hasil:", normalizePath(folder_hasil), "\n")
## Folder hasil: C:\Users\ASUS\OneDrive\Documents\hasil_searching_R_44302d02273e
# Pembahasan enam latihan pertemuan 11 ----
lat_x <- c(12, 7, 19, 7, 25)
# 11A Sequential Boolean posisi pertama 7.
print(seq_boolean(lat_x, 7))
## [1] 2
# 11B Tanpa Boolean target tidak ada dan larik kosong.
print(seq_tanpa_boolean(lat_x, 8))
## [1] NA
print(seq_tanpa_boolean(numeric(), 8))
## [1] NA
# 11C Terurut berhenti ketika nilai melebihi target.
print(seq_terurut(c(5, 10, 15, 20, 25), 12))
## [1] NA
# 11D Sentinel dan keutuhan data asli.
lat_awal <- lat_x
print(seq_sentinel(lat_x, 99))
## [1] NA
print(identical(lat_x, lat_awal))
## [1] TRUE
# 11E Posisi pertama berbeda dengan semua posisi.
print(match(7, lat_x))
## [1] 2
print(which(lat_x == 7))
## [1] 2 4
# 11F Data tidak sah ditolak dan pesan ditangkap.
print(tryCatch(seq_boolean(c(12, NA, 19), 19),
error = function(e) conditionMessage(e)))
## [1] "x harus larik numerik satu dimensi tanpa NA atau Inf"
# Pembahasan enam latihan pertemuan 12 ----
lat_urut <- seq(10, 100, by = 10)
# 12A Jejak pencarian 80.
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 Kasus batas pada kedua varian binary.
print(bin_boolean(lat_urut, 10))
## [1] 1
print(bin_tanpa_boolean(lat_urut, 100))
## [1] 10
print(bin_boolean(lat_urut, 105))
## [1] NA
# 12C Duplikasi dan posisi pertama.
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.
p <- bin_tanpa_boolean(produk_urut$kode, 103)
print(c(posisi_terurut = p, baris_asli = urutan[p]))
## posisi_terurut baris_asli
## 3 4
print(produk_urut[p, , drop = FALSE])
## kode nama stok
## 4 103 Minyak 30
# 12E Validasi menolak data yang belum terurut.
print(tryCatch(bin_boolean(c(30, 10, 20), 20),
error = function(e) conditionMessage(e)))
## [1] "Data harus terurut menaik"
# 12F Bandingkan kunjungan target terakhir.
print(c(sequential = kunjungan_sequential(seq_len(1024), 1024),
binary = nrow(jejak_binary(seq_len(1024), 1024))))
## sequential binary
## 1024 11