Latihan Soal Nomer 12 Algoritma Searching

# Pembahasan enam latihan pertemuan 12 ----
# 1. INISIALISASI VARIABEL & DATA DUMMY

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

# Inisialisasi data untuk latihan 12D (Tabel Produk)
urutan <- c(3, 1, 4, 2, 5, 6, 7, 8, 9, 10)
produk_urut <- data.frame(
  kode = seq(100, 190, by = 10),
  nama_produk = paste("Barang", 1:10)
)

# 2. DEFINISI FUNGSI PENDUKUNG (CUSTOM FUNCTIONS)
# Fungsi validasi: memeriksa apakah data sudah terurut
cek_terurut <- function(arr) {
  if (is.unsorted(arr)) {
    stop("Data belum terurut")
  }
}

# 12A & 12F. Jejak Binary Search (mengembalikan data frame langkah pencarian)
jejak_binary <- function(arr, target) {
  cek_terurut(arr)
  low <- 1
  high <- length(arr)
  jejak <- data.frame(low = integer(), high = integer(), mid = integer(), nilai = numeric())
  
  while (low <= high) {
    mid <- floor((low + high) / 2)
    jejak <- rbind(jejak, data.frame(low = low, high = high, mid = mid, nilai = arr[mid]))
    if (arr[mid] == target) {
      break
    } else if (arr[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(jejak)
}

# 12B, 12E. Binary Boolean (mengembalikan TRUE jika ada, FALSE jika tidak)
bin_boolean <- function(arr, target) {
  cek_terurut(arr)
  low <- 1
  high <- length(arr)
  while (low <= high) {
    mid <- floor((low + high) / 2)
    if (arr[mid] == target) {
      return(TRUE)
    } else if (arr[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(FALSE)
}

# 12B, 12D. Binary Tanpa Boolean (mengembalikan indeks posisi atau NA)
bin_tanpa_boolean <- function(arr, target) {
  cek_terurut(arr)
  low <- 1
  high <- length(arr)
  while (low <= high) {
    mid <- floor((low + high) / 2)
    if (arr[mid] == target) {
      return(mid)
    } else if (arr[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(NA)
}

# 12C. Binary Posisi Pertama (mencari kemunculan pertama pada data duplikat)
bin_pertama <- function(arr, target) {
  cek_terurut(arr)
  low <- 1
  high <- length(arr)
  result <- NA
  while (low <= high) {
    mid <- floor((low + high) / 2)
    if (arr[mid] == target) {
      result <- mid
      high <- mid - 1 # Lanjut telusuri ke kiri untuk indeks pertama
    } else if (arr[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(result)
}

# 12F. Menghitung jumlah kunjungan sequential search
kunjungan_sequential <- function(arr, target) {
  for (i in seq_along(arr)) {
    if (arr[i] == target) {
      return(i)
    }
  }
  return(length(arr))
}

# 3. PEMBAHASAN ENAM LATIHAN (PERTEMUAN 12)
lat_urut <- seq(10, 100, by = 10)
# 12A Jejak pencarian 80.
print(jejak_binary(lat_urut, 80))

##   low high mid nilai
## 1   1   10   5    50
## 2   6   10   8    80

# 12B Kasus batas pada kedua varian binary.
print(bin_boolean(lat_urut, 10))

## [1] TRUE

print(bin_tanpa_boolean(lat_urut, 100))

## [1] 10

print(bin_boolean(lat_urut, 105))

## [1] FALSE

# 12C Duplikasi dan posisi pertama.
print(bin_boolean(c(10, 20, 20, 20, 30), 20))

## [1] TRUE

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_asli1    baris_asli2    baris_asli3    baris_asli4 
##             NA             NA             NA             NA             NA 
##    baris_asli5    baris_asli6    baris_asli7    baris_asli8    baris_asli9 
##             NA             NA             NA             NA             NA 
##   baris_asli10 
##             NA

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

##      kode nama_produk
## NA     NA        <NA>
## NA.1   NA        <NA>
## NA.2   NA        <NA>
## NA.3   NA        <NA>
## NA.4   NA        <NA>
## NA.5   NA        <NA>
## NA.6   NA        <NA>
## NA.7   NA        <NA>
## NA.8   NA        <NA>
## NA.9   NA        <NA>

# 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