The binary search algorithm

This lesson covers implementing binary search in R, with the aim of understanding how to find a value efficiently.

Binary search finds a value efficiently in already-sorted data. Picture opening a dictionary in the middle and halving the range each time.

The sample code calculates the middle mid from the two positions low and high, compares it with the target, and narrows the range by updating low or high. %/% is R's integer division operator.

A common early stumble is that binary search requires the array to be sorted beforehand. That is a precondition, so do not forget to sort first.

In professional work, the idea behind binary search is applied widely wherever a particular value has to be found quickly in a large body of data.

📖 Reference code

binary_search <- function(arr, target) {
  low <- 1
  high <- length(arr)
  while (low <= high) {
    mid <- (low + high) %/% 2
    if (arr[mid] == target) {
      return(mid)
    } else if (arr[mid] < target) {
      low <- mid + 1
    } else {
      high <- mid - 1
    }
  }
  return(-1)
}

nums <- c(1, 3, 5, 7, 9, 11)
print(binary_search(nums, 7))
print(binary_search(nums, 4))

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run R directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).