# 1. Fungsi SeqSearch1 (tanpa variabel boolean)
SeqSearch1 <- function(L, x) {
i <- 1
n <- length(L)
while (i < n && L[i] != x) {
i <- i + 1
}
if (L[i] == x) {
return(i)
} else {
return(0)
}
}
# 2. Fungsi SeqSearch2 (menggunakan variabel boolean 'ketemu')
SeqSearch2 <- function(L, x) {
i <- 1
n <- length(L)
ketemu <- FALSE
while (i <= n && !ketemu) {
if (L[i] == x) {
ketemu <- TRUE
} else {
i <- i + 1
}
}
if (ketemu) {
return(i)
} else {
return(0)
}
}
# --- Pengujian Program ---
L <- c(7, 3, 9, 3, 5)
print(SeqSearch1(L, 3)) # Output: 2
## [1] 2
print(SeqSearch2(L, 3)) # Output: 2
## [1] 2
print(SeqSearch1(L, 8)) # Output: 0
## [1] 0
print(SeqSearch2(L, 8)) # Output: 0
## [1] 0
# 1. Fungsi BinSearch1 (berhenti segera saat nilai ditemukan)
BinSearch1 <- function(L, x) {
i <- 1
j <- length(L)
ketemu <- FALSE
while (i <= j && !ketemu) {
k <- floor((i + j) / 2)
if (L[k] == x) {
ketemu <- TRUE
} else if (x > L[k]) {
i <- k + 1 # Cari kanan
} else {
j <- k - 1 # Cari kiri
}
}
if (ketemu) {
return(k)
} else {
return(0)
}
}
# 2. Fungsi BinSearch2 (mempersempit rentang hingga tersisa 1 kandidat)
BinSearch2 <- function(L, x) {
i <- 1
j <- length(L)
while (i < j) {
k <- floor((i + j) / 2)
if (x > L[k]) {
i <- k + 1 # Cari kanan
} else {
j <- k # Persempit ke kiri (k tetap dipertahankan)
}
}
if (L[i] == x) {
return(i)
} else {
return(0)
}
}
# --- Pengujian Program ---
L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
print(BinSearch1(L, 23)) # Output: 6
## [1] 6
print(BinSearch1(L, 6)) # Output: 0
## [1] 0
print(BinSearch2(L, 23)) # Output: 6
## [1] 6
print(BinSearch2(L, 6)) # Output: 0
## [1] 0
binary_desc <- 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)
print(binary_desc(L, 23))
## [1] 5
print(binary_desc(L, 6))
## [1] 0
binary_rekursif <- function(L, x, i = 1, j = length(L)) {
if (i > j) {
return(0)
}
k <- (i + j) %/% 2
if (L[k] == x) {
return(k)
} else if (L[k] < x) {
return(binary_rekursif(L, x, k + 1, j))
} else {
return(binary_rekursif(L, x, i, k - 1))
}
}
L <- c(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
print(binary_rekursif(L, 23))
## [1] 6
print(binary_rekursif(L, 6))
## [1] 0
# Latihan Materi 2 Nomor 5 ----
# Binary Search dan Sequential Search
# 1. Mengambil data precip
data("precip")
# Mengambil nama kota
nama_kota <- names(precip)
# 2. Mengurutkan nama kota secara alfabetis
kota_urut <- sort(nama_kota)
cat("Nama kota setelah diurutkan:\n")
## Nama kota setelah diurutkan:
print(kota_urut)
## [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"
# 3. Fungsi Sequential Search
sequential_search <- function(data, target) {
perbandingan <- 0
for (i in seq_along(data)) {
perbandingan <- perbandingan + 1
if (data[i] == target) {
return(list(
hasil = target,
posisi = i,
perbandingan = perbandingan
))
}
}
return(list(
hasil = "Tidak ditemukan",
posisi = NA,
perbandingan = perbandingan
))
}
# 4. Fungsi Binary Search
binary_search <- function(data, target) {
kiri <- 1
kanan <- length(data)
perbandingan <- 0
while (kiri <= kanan) {
tengah <- floor((kiri + kanan) / 2)
perbandingan <- perbandingan + 1
if (data[tengah] == target) {
return(list(
hasil = target,
posisi = tengah,
perbandingan = perbandingan
))
} else if (data[tengah] < target) {
kiri <- tengah + 1
} else {
kanan <- tengah - 1
}
}
return(list(
hasil = "Tidak ditemukan",
posisi = NA,
perbandingan = perbandingan
))
}
# 5. Mencari Seattle dan Tacoma
target <- c("Seattle", "Tacoma")
for (kota in target) {
cat("\n================================\n")
cat("Pencarian kota:", kota, "\n")
hasil_sequential <- sequential_search(
nama_kota, kota
)
hasil_binary <- binary_search(
kota_urut, kota
)
cat("\nSequential Search:\n")
print(hasil_sequential)
cat("\nBinary Search:\n")
print(hasil_binary)
}
##
## ================================
## Pencarian kota: Seattle
##
## Sequential Search:
## $hasil
## [1] "Tidak ditemukan"
##
## $posisi
## [1] NA
##
## $perbandingan
## [1] 70
##
##
## Binary Search:
## $hasil
## [1] "Tidak ditemukan"
##
## $posisi
## [1] NA
##
## $perbandingan
## [1] 6
##
##
## ================================
## Pencarian kota: Tacoma
##
## Sequential Search:
## $hasil
## [1] "Tidak ditemukan"
##
## $posisi
## [1] NA
##
## $perbandingan
## [1] 70
##
##
## Binary Search:
## $hasil
## [1] "Tidak ditemukan"
##
## $posisi
## [1] NA
##
## $perbandingan
## [1] 6
# 6. Membandingkan jumlah perbandingan
hasil_perbandingan <- data.frame(
Kota = target,
Sequential_Search = sapply(
target,
function(k) sequential_search(nama_kota, k)$perbandingan
),
Binary_Search = sapply(
target,
function(k) binary_search(kota_urut, k)$perbandingan
)
)
cat("\nTabel Perbandingan:\n")
##
## Tabel Perbandingan:
print(hasil_perbandingan)
## Kota Sequential_Search Binary_Search
## Seattle Seattle 70 6
## Tacoma Tacoma 70 6