Algoritma Pencarian/Searching

#1 & 2 Penelusuran SeqSearch1, SeqSearch2, dan Simulasi Tanpa Short-Circuit
seq_search_1_trace_r <- function(L, x) {
  n <- length(L)
  i <- 1
  cat("--- R: SeqSearch1 untuk x =", x, "---\n")
  while ((i <= n) && (L[i] != x)) {
    cat("Putaran i =", i, ", L[", i, "] =", L[i], "!=", x, "\n")
    i <- i + 1
  }
  if ((i <= n) && (L[i] == x)) {
    cat("Ketemu di indeks ke-", i, "\n")
    return(i)
  } else {
    cat("Tidak ditemukan (idx = 0)\n")
    return(0)
  }
}

seq_search_2_trace_r <- function(L, x) {
  n <- length(L)
  i <- 1
  ketemu <- FALSE
  cat("\n--- R: SeqSearch2 untuk x =", x, "---\n")
  while ((i <= n) && (!ketemu)) {
    cat("Putaran i =", i, ", L[", i, "] =", L[i], "\n")
    if (L[i] == x) {
      ketemu <- TRUE
    } else {
      i <- i + 1
    }
  }
  if (ketemu) {
    cat("Ketemu di indeks ke-", i, "\n")
    return(i)
  } else {
    cat("Tidak ditemukan (idx = 0)\n")
    return(0)
  }
}

# Uji Coba R
L_data_r <- c(7, 3, 9, 3, 5)
seq_search_1_trace_r(L_data_r, 3)

## --- R: SeqSearch1 untuk x = 3 ---
## Putaran i = 1 , L[ 1 ] = 7 != 3 
## Ketemu di indeks ke- 2

## [1] 2

seq_search_2_trace_r(L_data_r, 8)

## 
## --- R: SeqSearch2 untuk x = 8 ---
## Putaran i = 1 , L[ 1 ] = 7 
## Putaran i = 2 , L[ 2 ] = 3 
## Putaran i = 3 , L[ 3 ] = 9 
## Putaran i = 4 , L[ 4 ] = 3 
## Putaran i = 5 , L[ 5 ] = 5 
## Tidak ditemukan (idx = 0)

## [1] 0

# 3. Penelusuran Binary Search (BinSearch1 & BinSearch2)
bin_search_trace_r <- function(L, x) {
  i <- 1
  j <- length(L)
  cat("\n--- R: Binary Search untuk x =", x, "---\n")
  langkah <- 1
  while (i <= j) {
    k <- floor((i + j) / 2)
    cat("Langkah", langkah, ": i =", i, ", j =", j, ", k =", k, "(L[k] =", L[k], ")\n")
    if (L[k] == x) {
      cat("Ketemu di indeks ke-", k, "\n")
      return(k)
    } else if (L[k] < x) {
      i <- k + 1
    } else {
      j <- k - 1
    }
    langkah <- langkah + 1
  }
  cat("Tidak ditemukan.\n")
  return(0)
}

# Uji Coba R
L_bin_r <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
bin_search_trace_r(L_bin_r, 23)

## 
## --- R: Binary Search untuk x = 23 ---
## Langkah 1 : i = 1 , j = 10 , k = 5 (L[k] = 16 )
## Langkah 2 : i = 6 , j = 10 , k = 8 (L[k] = 56 )
## Langkah 3 : i = 6 , j = 7 , k = 6 (L[k] = 23 )
## Ketemu di indeks ke- 6

## [1] 6

bin_search_trace_r(L_bin_r, 6)

## 
## --- R: Binary Search untuk x = 6 ---
## Langkah 1 : i = 1 , j = 10 , k = 5 (L[k] = 16 )
## Langkah 2 : i = 1 , j = 4 , k = 2 (L[k] = 5 )
## Langkah 3 : i = 3 , j = 4 , k = 3 (L[k] = 8 )
## Tidak ditemukan.

## [1] 0

# 4. Binary Search untuk Larik Terurut Menurun (Descending)
bin_search_desc_r <- function(L, x) {
  i <- 1
  j <- length(L)
  while (i <= j) {
    k <- floor((i + j) / 2)
    if (L[k] == x) {
      return(k)
    } else if (L[k] < x) {
      j <- k - 1  # Dibalik untuk descending
    } else {
      i <- k + 1
    }
  }
  return(0)
}

# Uji Coba R
L_desc_r <- c(91, 72, 56, 38, 23, 16, 12, 8, 5, 2)
print(paste("\nR Descending Index:", bin_search_desc_r(L_desc_r, 23))) # Output: 5

## [1] "\nR Descending Index: 5"

#5: Pencarian "Seattle Tacoma" pada Data precip
# Menggunakan dataset bawaan R
data("precip")
kota_terurut_r <- sort(names(precip))

bin_search_string_r <- function(arr, target) {
  i <- 1
  j <- length(arr)
  cmp <- 0
  while (i <= j) {
    cmp <- cmp + 1
    k <- floor((i + j) / 2)
    if (arr[k] == target) {
      return(list(index = k, comparisons = cmp))
    } else if (arr[k] < target) {
      i <- k + 1
    } else {
      j <- k - 1
    }
  }
  return(list(index = 0, comparisons = cmp))
}

hasil_r <- bin_search_string_r(kota_terurut_r, "Seattle Tacoma")
cat(
  "\nR - Seattle Tacoma ditemukan di indeks:",
  hasil_r$index,
  "dengan",
  hasil_r$comparisons,
  "perbandingan.\n"
)

## 
## R - Seattle Tacoma ditemukan di indeks: 64 dengan 5 perbandingan.

#6. Fungsi Binary Search Rekursif
bin_search_rekursif_r <- function(L, x, i, j) {
  if (i > j) {
    return(0)
  }
  k <- floor((i + j) / 2)
  if (L[k] == x) {
    return(k)
  } else if (L[k] < x) {
    return(bin_search_rekursif_r(L, x, k + 1, j))
  } else {
    return(bin_search_rekursif_r(L, x, i, k - 1))
  }
}

# Uji Coba R
L_rek_r <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
cat(
  "\nR Rekursif (Cari 23): Indeks ke-",
  bin_search_rekursif_r(L_rek_r, 23, 1, length(L_rek_r)),
  "\n"
)

## 
## R Rekursif (Cari 23): Indeks ke- 6

#7. Perhitungan Perbandingan Maksimum Binary Search (\bm{n = 1.000.000})
n <- 1000000
max_cmp_r <- floor(log2(n)) + 1
cat(
  "\nR - Untuk n =",
  format(n, big.mark = ","),
  ", max perbandingan Binary Search =",
  max_cmp_r,
  "\n"
)

## 
## R - Untuk n = 1e+06 , max perbandingan Binary Search = 20