Tugas No12 Algoritma Searching

# Pembahasan enam latihan pertemuan 12 ----

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


# 12A Jejak pencarian 80.

validasi_urut <- function(data) {
  if (anyNA(data)) {
    stop("Data tidak boleh mengandung NA")
  }

  if (is.unsorted(data)) {
    stop("Data harus terurut")
  }
}

jejak_binary <- function(data, target) {
  validasi_urut(data)

  kiri <- 1
  kanan <- length(data)

  jejak <- data.frame(
    iterasi = integer(),
    kiri = integer(),
    kanan = integer(),
    tengah = integer(),
    nilai_tengah = numeric()
  )

  iterasi <- 0

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

    jejak <- rbind(
      jejak,
      data.frame(
        iterasi = iterasi,
        kiri = kiri,
        kanan = kanan,
        tengah = tengah,
        nilai_tengah = data[tengah]
      )
    )

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

  return(jejak)
}

print(jejak_binary(lat_urut, 80))

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

# 12B Kasus batas pada kedua varian binary.

bin_boolean <- function(data, target) {
  validasi_urut(data)

  kiri <- 1
  kanan <- length(data)
  ketemu <- FALSE
  posisi <- 0

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

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

  return(posisi)
}

bin_tanpa_boolean <- function(data, target) {
  validasi_urut(data)

  kiri <- 1
  kanan <- length(data)

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

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

  return(0)
}

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.

bin_pertama <- function(data, target) {
  validasi_urut(data)

  kiri <- 1
  kanan <- length(data)
  posisi <- 0

  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
    }
  }

  return(posisi)
}

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.

# Membuat contoh tabel produk
produk <- data.frame(
  kode = c(105, 101, 103, 102, 104),
  nama_produk = c(
    "Produk A",
    "Produk B",
    "Produk C",
    "Produk D",
    "Produk E"
  )
)

# Mengurutkan tabel berdasarkan kode
urutan <- order(produk$kode)

produk_urut <- produk[urutan, ]

# Mencari kode 103
p <- bin_tanpa_boolean(produk_urut$kode, 103)

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

## posisi_terurut     baris_asli 
##              3              3

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

##   kode nama_produk
## 3  103    Produk C

# 12E Validasi menolak data yang belum terurut.

print(
  tryCatch(
    bin_boolean(c(30, 10, 20), 20),
    error = function(e) conditionMessage(e)
  )
)

## [1] "Data harus terurut"

# 12F Bandingkan kunjungan target terakhir.

kunjungan_sequential <- function(data, target) {
  i <- 1
  jumlah <- 0

  while (i <= length(data)) {
    jumlah <- jumlah + 1

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

    i <- i + 1
  }

  return(jumlah)
}

print(
  c(
    sequential = kunjungan_sequential(seq_len(1024), 1024),
    binary = nrow(jejak_binary(seq_len(1024), 1024))
  )
)

## sequential     binary 
##       1024         11