tugas latihan 12

# 12A — Binary search yang merekam jejak (lo, hi, mid) tiap iterasi
jejak_binary <- function(x, target) {
  lo <- 1; hi <- length(x)
  jejak <- data.frame(iterasi = integer(), lo = integer(),
                      hi = integer(), mid = integer(), nilai = numeric())
  it <- 0
  while (lo <= hi) {
    it <- it + 1
    mid <- (lo + hi) %/% 2
    jejak <- rbind(jejak, data.frame(iterasi = it, lo = lo, hi = hi,
                                     mid = mid, nilai = x[mid]))
    if (x[mid] == target) return(jejak)
    if (x[mid] < target) lo <- mid + 1 else hi <- mid - 1
  }
  return(jejak)   # tidak ditemukan: jejak sampai lo > hi
}

# 12B — Binary search dengan flag boolean
bin_boolean <- function(x, target) {
  if (is.unsorted(x)) stop("Data belum terurut")
  lo <- 1; hi <- length(x); ketemu <- FALSE; pos <- 0
  while (lo <= hi && !ketemu) {
    mid <- (lo + hi) %/% 2
    if (x[mid] == target) { ketemu <- TRUE; pos <- mid }
    else if (x[mid] < target) lo <- mid + 1
    else hi <- mid - 1
  }
  return(pos)     # 0 jika tidak ditemukan
}

# 12B — Binary search tanpa boolean (return langsung)
bin_tanpa_boolean <- function(x, target) {
  if (is.unsorted(x)) stop("Data belum terurut")
  lo <- 1; hi <- length(x)
  while (lo <= hi) {
    mid <- (lo + hi) %/% 2
    if (x[mid] == target) return(mid)
    if (x[mid] < target) lo <- mid + 1 else hi <- mid - 1
  }
  return(0)
}

# 12C — Binary search yang kembali ke posisi PERTAMA duplikat
bin_pertama <- function(x, target) {
  lo <- 1; hi <- length(x); hasil <- 0
  while (lo <= hi) {
    mid <- (lo + hi) %/% 2
    if (x[mid] == target) { hasil <- mid; hi <- mid - 1 }  # cari ke kiri
    else if (x[mid] < target) lo <- mid + 1
    else hi <- mid - 1
  }
  return(hasil)
}

# 12F — Hitung kunjungan sequential untuk target
kunjungan_sequential <- function(x, target) {
  for (i in seq_along(x)) if (x[i] == target) return(i)
  return(length(x))
}

# Data produk (contoh): kode terurut + pemetaan ke baris asli
produk_asli <- data.frame(kode = c(101, 103, 102, 105, 104),
                          nama = c("A", "B", "C", "D", "E"))
urutan <- order(produk_asli$kode)          # baris asli urut kode
produk_urut <- produk_asli[urutan, , drop = FALSE]

# Pembahasan enam latihan pertemuan 12 ----
lat_urut <- seq(10, 100, by = 10)
# 12A Jejak pencarian 80.
print(jejak_binary(lat_urut, 80))

##   iterasi lo hi mid nilai
## 1       1  1 10   5    50
## 2       2  6 10   8    80

# 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] 0

# 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              2

print(produk_urut[p, , drop = FALSE])

##   kode nama
## 2  103    B

# 12E Validasi menolak data yang belum terurut.
print(tryCatch(bin_boolean(c(30, 10, 20), 20),
  error = function(e) conditionMessage(e)))

## [1] "Data belum terurut"

# 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