Pembahasan 12

# DEFINISI FUNGSI

validasi_binary <- function(x) {
  if (any(is.na(x))) stop("Data mengandung NA / nilai hilang!")
  if (is.unsorted(x)) stop("Data belum terurut menaik!")
}

jejak_binary <- function(x, target) {
  validasi_binary(x)
  low <- 1
  high <- length(x)
  langkah <- data.frame(langkah = integer(), low = integer(), high = integer(), mid = integer(), val_mid = numeric())
  step <- 1
  while (low <= high) {
    mid <- (low + high) %/% 2
    langkah <- rbind(langkah, data.frame(langkah = step, low = low, high = high, mid = mid, val_mid = x[mid]))
    if (x[mid] == target) {
      break
    } else if (x[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
    step <- step + 1
  }
  return(langkah)
}

bin_boolean <- function(x, target) {
  validasi_binary(x)
  low <- 1
  high <- length(x)
  ketemu <- FALSE
  posisi <- NA
  while (low <= high && !ketemu) {
    mid <- (low + high) %/% 2
    if (x[mid] == target) {
      ketemu <- TRUE
      posisi <- mid
    } else if (x[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(posisi)
}

bin_tanpa_boolean <- function(x, target) {
  validasi_binary(x)
  low <- 1
  high <- length(x)
  while (low <= high) {
    mid <- (low + high) %/% 2
    if (x[mid] == target) {
      return(mid)
    } else if (x[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(NA)
}

bin_pertama <- function(x, target) {
  validasi_binary(x)
  low <- 1
  high <- length(x)
  posisi <- NA
  while (low <= high) {
    mid <- (low + high) %/% 2
    if (x[mid] == target) {
      posisi <- mid
      high <- mid - 1 
    } else if (x[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(posisi)
}

kunjungan_sequential <- function(x, target) {
  kunjungan <- 0
  for (i in seq_along(x)) {
    kunjungan <- kunjungan + 1
    if (x[i] == target) break
  }
  return(kunjungan)
}

produk_asli <- data.frame(
  kode = c(101, 105, 102, 103, 104),
  nama = c("Beras", "Gula", "Telur", "Minyak", "Tepung"),
  stok = c(50, 20, 40, 30, 15),
  stringsAsFactors = FALSE
)
urutan <- order(produk_asli$kode)
produk_urut <- produk_asli[urutan, ]
rownames(produk_urut) <- NULL

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

##   langkah low high mid val_mid
## 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] 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
## 3  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 belum 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