# 1. Menelusuri SeqSearch1 dan SeqSearch2
seq_search1 <- function(L, x) {
n <- length(L)
i <- 1
while (i < n && L[i] != x) {
i <- i + 1
}
if (n > 0 && L[i] == x) {
return(i)
} else {
return(0)
}
}
# Sequential Search 2 (dengan boolean)
seq_search2 <- function(L, x) {
n <- length(L)
i <- 1
ketemu <- FALSE
while (i <= n && !ketemu) {
if (L[i] == x) {
ketemu <- TRUE
} else {
i <- i + 1
}
}
if (ketemu) {
return(i)
} else {
return(0)
}
}
# Program utama
L <- c(7, 3, 9, 3, 5)
cat("SEQSEARCH1\n")
## SEQSEARCH1
cat("x = 3:", seq_search1(L, 3), "\n")
## x = 3: 2
cat("x = 8:", seq_search1(L, 8), "\n")
## x = 8: 0
cat("\nSEQSEARCH2\n")
##
## SEQSEARCH2
cat("x = 3:", seq_search2(L, 3), "\n")
## x = 3: 2
cat("x = 8:", seq_search2(L, 8), "\n")
## x = 8: 0
# 2. Apa yang terjadi jika tidak menggunakan short-circuit?
L <- c(7, 3, 9, 3, 5)
x <- 8
i <- 1
n <- length(L)
ketemu <- FALSE
while (i <= n) {
if (L[i] == x) {
ketemu <- TRUE
break
} else {
i <- i + 1
}
}
if (ketemu) {
print("Data ditemukan")
} else {
print("Data tidak ditemukan")
}
## [1] "Data tidak ditemukan"
# 3. Menelusuri BinSearch1 dan BinSearch2
bin_search1 <- function(L, x) {
i <- 1
j <- length(L)
ketemu <- FALSE
k <- 0
while (!ketemu && i <= j) {
k <- (i + j) %/% 2
if (L[k] == x) {
ketemu <- TRUE
} else if (L[k] < x) {
i <- k + 1
} else {
j <- k - 1
}
}
if (ketemu) {
return(k)
} else {
return(0)
}
}
# Binary Search 2 (tanpa boolean)
bin_search2 <- function(L, x) {
i <- 1
j <- length(L)
while (i < j) {
k <- (i + j) %/% 2
if (L[k] < x) {
i <- k + 1
} else {
j <- k
}
}
if (L[i] == x) {
return(i)
} else {
return(0)
}
}
# Program utama
L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
cat("BINSEARCH1\n")
## BINSEARCH1
for (x in c(23, 6)) {
cat("x =", x, "posisi =", bin_search1(L, x), "\n")
}
## x = 23 posisi = 6
## x = 6 posisi = 0
cat("\nBINSEARCH2\n")
##
## BINSEARCH2
for (x in c(23, 6)) {
cat("x =", x, "posisi =", bin_search2(L, x), "\n")
}
## x = 23 posisi = 6
## x = 6 posisi = 0
# 4. Mengubah Binary Search agar bekerja pada larik terurut menurun
binary_menurun <- function(L, x) {
i <- 1
j <- length(L)
while (i <= j) {
k <- (i + j) %/% 2
if (L[k] == x) {
return(k)
} else if (L[k] > x) {
i <- k + 1
} else {
j <- k - 1
}
}
return(0)
}
L <- c(91, 72, 56, 38, 23, 16, 12, 8, 5, 2)
cat("Posisi 23:", binary_menurun(L, 23), "\n")
## Posisi 23: 5
cat("Posisi 6:", binary_menurun(L, 6), "\n")
## Posisi 6: 0
# 5. Dataset precip dan Pencarian Seattle Tacoma
# Memanggil dataset precip
data(precip)
# Mengambil nama kota
kota <- names(precip)
# Menyimpan data asli
kota_asli <- kota
# =================================
# BUBBLE SORT (URUT ALFABETIS)
# =================================
n <- length(kota)
for (i in 1:(n - 1)) {
for (j in 1:(n - i)) {
if (kota[j] > kota[j + 1]) {
temp <- kota[j]
kota[j] <- kota[j + 1]
kota[j + 1] <- temp
}
}
}
cat("Nama kota setelah diurutkan:\n")
## Nama kota setelah diurutkan:
print(kota)
## [1] "Albany" "Albuquerque" "Atlanta"
## [4] "Atlantic City" "Baltimore" "Bismarck"
## [7] "Boise" "Boston" "Buffalo"
## [10] "Burlington" "Charleston" "Charlotte"
## [13] "Cheyenne" "Chicago" "Cincinnati"
## [16] "Cleveland" "Columbia" "Columbus"
## [19] "Concord" "Dallas" "Denver"
## [22] "Des Moines" "Detroit" "Duluth"
## [25] "El Paso" "Great Falls" "Hartford"
## [28] "Honolulu" "Houston" "Indianapolis"
## [31] "Jackson" "Jacksonville" "Juneau"
## [34] "Kansas City" "Little Rock" "Los Angeles"
## [37] "Louisville" "Memphis" "Miami"
## [40] "Milwaukee" "Minneapolis/St Paul" "Mobile"
## [43] "Nashville" "New Orleans" "New York"
## [46] "Norfolk" "Oklahoma City" "Omaha"
## [49] "Peoria" "Philadelphia" "Phoenix"
## [52] "Pittsburgh" "Portland" "Portland"
## [55] "Providence" "Raleigh" "Reno"
## [58] "Richmond" "Sacramento" "Salt Lake City"
## [61] "San Francisco" "San Juan" "Sault Ste. Marie"
## [64] "Seattle Tacoma" "Sioux Falls" "Spokane"
## [67] "St Louis" "Washington" "Wichita"
## [70] "Wilmington"
# =================================
# BINARY SEARCH
# =================================
binary_search <- function(L, x) {
i <- 1
j <- length(L)
perbandingan <- 0
while (i <= j) {
k <- (i + j) %/% 2
perbandingan <- perbandingan + 1
if (L[k] == x) {
return(c(posisi = k,
perbandingan = perbandingan))
} else if (L[k] < x) {
i <- k + 1
} else {
j <- k - 1
}
}
return(c(posisi = 0,
perbandingan = perbandingan))
}
# =================================
# SEQUENTIAL SEARCH
# =================================
sequential_search <- function(L, x) {
perbandingan <- 0
for (i in seq_along(L)) {
perbandingan <- perbandingan + 1
if (L[i] == x) {
return(c(posisi = i,
perbandingan = perbandingan))
}
}
return(c(posisi = 0,
perbandingan = perbandingan))
}
# Nilai yang dicari
target <- "Seattle Tacoma"
# Menjalankan pencarian
hasil_binary <- binary_search(kota, target)
hasil_sequential <- sequential_search(
kota_asli, target
)
# Menampilkan hasil
cat("\nHASIL BINARY SEARCH\n")
##
## HASIL BINARY SEARCH
print(hasil_binary)
## posisi perbandingan
## 64 5
cat("\nHASIL SEQUENTIAL SEARCH\n")
##
## HASIL SEQUENTIAL SEARCH
print(hasil_sequential)
## posisi perbandingan
## 65 65
# 6. Binary Search Rekursif dalam R
binary_recursive <- function(L, x, i = 1, j = length(L)) {
# Kondisi berhenti
if (i > j) {
return(0)
}
k <- (i + j) %/% 2
if (L[k] == x) {
return(k)
} else if (L[k] < x) {
return(
binary_recursive(L, x, k + 1, j)
)
} else {
return(
binary_recursive(L, x, i, k - 1)
)
}
}
# Program utama
L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
cat("x = 23:", binary_recursive(L, 23), "\n")
## x = 23: 6
cat("x = 6:", binary_recursive(L, 6), "\n")
## x = 6: 0
# 7. Perbandingan Maksimum Binary Search
n <- 1000000
perbandingan <- floor(log2(n)) + 1
cat("Jumlah data:", n, "\n")
## Jumlah data: 1e+06
cat("Perbandingan maksimum:", perbandingan, "\n")
## Perbandingan maksimum: 20