# 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