Algoritma Pemrograman Searching & Sorting Latihan 12

# Validasi data
validasi <- function(data) {
  if (!is.numeric(data) || any(is.na(data)) ||
      is.unsorted(data)) {
    stop("Data harus numerik, tidak mengandung NA, dan terurut")
  }
}

# Jejak Binary Search
jejak_binary <- function(data, target) {
  validasi(data)
  kiri <- 1
  kanan <- length(data)
  hasil <- data.frame()

  while (kiri <= kanan) {
    tengah <- floor((kiri + kanan) / 2)
    hasil <- rbind(hasil, data.frame(
      kiri, kanan, tengah, nilai_tengah = data[tengah]
    ))

    if (data[tengah] == target) break
    if (data[tengah] < target) kiri <- tengah + 1
    else kanan <- tengah - 1
  }
  hasil
}

# Binary Search dengan Boolean
bin_boolean <- function(data, target) {
  validasi(data)
  kiri <- 1
  kanan <- length(data)
  posisi <- NA
  ditemukan <- FALSE

  while (kiri <= kanan && !ditemukan) {
    tengah <- floor((kiri + kanan) / 2)

    if (data[tengah] == target) {
      posisi <- tengah
      ditemukan <- TRUE
    } else if (data[tengah] < target) {
      kiri <- tengah + 1
    } else kanan <- tengah - 1
  }
  posisi
}

# Binary Search tanpa Boolean
bin_tanpa_boolean <- function(data, target) {
  validasi(data)
  kiri <- 1
  kanan <- length(data)

  while (kiri <= kanan) {
    tengah <- floor((kiri + kanan) / 2)

    if (data[tengah] == target) return(tengah)
    if (data[tengah] < target) kiri <- tengah + 1
    else kanan <- tengah - 1
  }
  NA
}

# Binary Search posisi pertama
bin_pertama <- function(data, target) {
  validasi(data)
  kiri <- 1
  kanan <- length(data)
  posisi <- NA

  while (kiri <= kanan) {
    tengah <- floor((kiri + kanan) / 2)

    if (data[tengah] == target) {
      posisi <- tengah
      kanan <- tengah - 1
    } else if (data[tengah] < target) {
      kiri <- tengah + 1
    } else kanan <- tengah - 1
  }
  posisi
}

# Menghitung kunjungan Sequential Search
kunjungan_sequential <- function(data, target) {
  for (i in seq_along(data)) {
    if (data[i] == target) return(i)
  }
  length(data)
}

# Data produk
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)
)

# Persiapan tabel produk untuk 12D
urutan <- order(produk$kode)
produk_urut <- produk[urutan, ]


# Pembahasan enam latihan pertemuan 12 ----

lat_urut <- seq(10, 100, by = 10)

# 12A Jejak pencarian 80
print(jejak_binary(lat_urut, 80))

##   kiri kanan tengah nilai_tengah
## 1    1    10      5           50
## 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)

if (!is.na(p)) {
  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              4 
##   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 numerik, tidak mengandung NA, dan 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