Algoritma dan pemrograman latihan 2

# ===== Nomor 1: Sequential search =====
seq_search1 <- function(L, x) {
  n <- length(L); i <- 1
  while (i <= n && L[i] != x) i <- i + 1     # && = short-circuit
  if (i <= n) i else 0
}

seq_search2 <- function(L, x) {              # versi sentinel
  n <- length(L)
  A <- c(L, x)
  i <- 1
  while (A[i] != x) i <- i + 1
  if (i <= n) i else 0
}

A <- c(7, 3, 9, 3, 5)
seq_search1(A, 3); seq_search1(A, 8)         # 2  0

## [1] 2

## [1] 0

seq_search2(A, 3); seq_search2(A, 8)         # 2  0

## [1] 2

## [1] 0

# ===== Nomor 2: tanpa short-circuit =====
# while (i <= n & L[i] != x)   # & = tanpa short-circuit; L[n+1] = NA, tetap aman

# ===== Nomor 3: Binary search =====
bin_search1 <- function(L, x) {
  low <- 1; high <- length(L)
  while (low <= high) {
    mid <- (low + high) %/% 2
    if (L[mid] == x)      return(mid)
    else if (L[mid] < x)  low <- mid + 1
    else                  high <- mid - 1
  }
  0
}

bin_search2 <- function(L, x) {
  low <- 1; high <- length(L)
  while (low < high) {
    mid <- (low + high) %/% 2
    if (L[mid] < x) low <- mid + 1 else high <- mid
  }
  if (L[low] == x) low else 0
}

B <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
bin_search1(B, 23); bin_search1(B, 6)        # 6  0

## [1] 6

## [1] 0

bin_search2(B, 23); bin_search2(B, 6)        # 6  0

## [1] 6

## [1] 0

# ===== Nomor 4: Larik menurun =====
bin_search_desc <- function(L, x) {
  low <- 1; high <- length(L)
  while (low <= high) {
    mid <- (low + high) %/% 2
    if (L[mid] == x)      return(mid)
    else if (L[mid] > x)  low <- mid + 1     # tanda dibalik
    else                  high <- mid - 1
  }
  0
}

bin_search_desc(rev(B), 23)                  # 5

## [1] 5

# ===== Nomor 5: Data precip =====
kota   <- sort(names(precip))
target <- "Seattle Tacoma"

low <- 1; high <- length(kota); banding_bin <- 0; hasil <- 0
while (low <= high) {
  mid <- (low + high) %/% 2
  banding_bin <- banding_bin + 1
  if (kota[mid] == target) { hasil <- mid; break }
  else if (kota[mid] < target) low <- mid + 1
  else high <- mid - 1
}

banding_seq <- 0
for (i in seq_along(kota)) {
  banding_seq <- banding_seq + 1
  if (kota[i] == target) break
}

cat("Indeks:", hasil, "\n")

## Indeks: 64

cat("Binary search    :", banding_bin, "perbandingan\n")

## Binary search    : 5 perbandingan

cat("Sequential search:", banding_seq, "perbandingan\n")

## Sequential search: 64 perbandingan

# ===== Nomor 6: Rekursif =====
bin_search_rek <- function(L, x, low = 1, high = length(L)) {
  if (low > high) return(0)
  mid <- (low + high) %/% 2
  if (L[mid] == x)      return(mid)
  else if (L[mid] < x)  return(bin_search_rek(L, x, mid + 1, high))
  else                  return(bin_search_rek(L, x, low, mid - 1))
}

bin_search_rek(B, 23)                        # 6

## [1] 6

bin_search_rek(B, 6)                         # 0

## [1] 0