Pembahasan Pertemuan 12

Pembahasan Pertemuan 12

Materi ini membahas Binary Search, yaitu pencarian data pada vektor yang sudah terurut menaik.

Data latihan

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

##  [1]  10  20  30  40  50  60  70  80  90 100

Fungsi validasi

validasi_binary <- function(x, target) {
  if (anyNA(x)) {
    stop("Data tidak boleh mengandung NA")
  }

  if (is.unsorted(x, strictly = FALSE)) {
    stop("Data harus terurut menaik")
  }

  if (length(target) != 1 || is.na(target)) {
    stop("Target harus satu nilai dan tidak boleh NA")
  }
}

Latihan 12A – Jejak Binary Search

jejak_binary <- function(x, target) {
  validasi_binary(x, target)

  kiri <- 1
  kanan <- length(x)
  langkah <- data.frame(
    kiri = integer(),
    kanan = integer(),
    tengah = integer(),
    nilai = numeric()
  )

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

    langkah <- rbind(
      langkah,
      data.frame(
        kiri = kiri,
        kanan = kanan,
        tengah = tengah,
        nilai = x[tengah]
      )
    )

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

  langkah
}

print(jejak_binary(lat_urut, 80))

##   kiri kanan tengah nilai
## 1    1    10      5    50
## 2    6    10      8    80

Latihan 12B – Binary Boolean dan Tanpa Boolean

bin_boolean <- function(x, target) {
  validasi_binary(x, target)

  kiri <- 1
  kanan <- length(x)

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

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

  NA_integer_
}

bin_tanpa_boolean <- function(x, target) {
  validasi_binary(x, target)

  kiri <- 1
  kanan <- length(x)

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

    if (x[tengah] == target) {
      return(tengah)
    }

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

  NA_integer_
}

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

Latihan 12C – Data Duplikat dan Posisi Pertama

bin_pertama <- function(x, target) {
  validasi_binary(x, target)

  kiri <- 1
  kanan <- length(x)
  hasil <- NA_integer_

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

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

  hasil
}

data_duplikat <- c(10, 20, 20, 20, 30)

print(bin_boolean(data_duplikat, 20))

## [1] 3

print(bin_pertama(data_duplikat, 20))

## [1] 2

Latihan 12D – Pencarian Kode Produk

Bagian ini menggunakan objek produk_urut dan urutan dari praktikum sebelumnya. Jalankan atau buat kedua objek tersebut terlebih dahulu.

p <- bin_tanpa_boolean(produk_urut$kode, 103)

print(c(
  posisi_terurut = p,
  baris_asli = urutan[p]
))

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

Latihan 12E – Validasi Data Tidak Terurut

hasil_galat <- tryCatch(
  bin_boolean(c(30, 10, 20), 20),
  error = function(e) conditionMessage(e)
)

print(hasil_galat)

## [1] "Data harus terurut menaik"

Latihan 12F – Perbandingan Jumlah Kunjungan

kunjungan_sequential <- function(x, target) {
  if (anyNA(x)) {
    stop("Data tidak boleh mengandung NA")
  }

  jumlah <- 0

  for (i in seq_along(x)) {
    jumlah <- jumlah + 1

    if (x[i] == target) {
      return(jumlah)
    }
  }

  jumlah
}

hasil_perbandingan <- c(
  sequential = kunjungan_sequential(seq_len(1024), 1024),
  binary = nrow(jejak_binary(seq_len(1024), 1024))
)

print(hasil_perbandingan)

## sequential     binary 
##       1024         11