## R Language Binary Search

I made a commitment to increase my R language programming skills by creating a bunch of succinct examples. In many languages, an array binary search function has lots of interesting nuances.

Here’s a binary vector search (weirdly, in R an ‘array’ is a matrix with three or more dimensions) function:

The function definition skeleton is:

# binsearch.R
# R 3.2.4
bin_search = function(v, t, eps) {
lo = as.integer(1)
hi = length(v)
while (lo ≤ hi) {
. . .
return(0)
}

Parameter v is a sorted numeric vector, Parameter t is a target value to search for. Parameter eps is an epsilon threshold used when determining if two floating point values are equal or not.

Variable lo is the beginning index — R is 1-based unlike most other languages which are 0-based.

The body of the while loop is:

mid = as.integer(round((lo + hi) / 2)) # always even!
cat("lo, mid, hi = ", lo, mid, hi, "\n")

if (abs(v[mid] - t) ≤ eps) {
return(mid)
}
else if (v[mid] < t) { # C format OK in a function
lo = mid + 1
}
else {
hi = mid - 1
}

Calculating the mid index is tricky. Without the call to the round() function, the as.integer() function of x.5 sometimes rounds down to x and sometimes up to x+1. Strangely, the round() function in R always rounds to the nearest even integer.

Inside a function, you can write code like:

if (a == b) {
# something
}
else if (c == d) {
# something else
}

But outside a code block you must place the if close-curly the else on the same line like so:

if (a == b) {
# something
} else if (c == d) {
# something else
}

The function returns 0, which is an invalid vector index to indicate target-not-found rather than -1 used in most languages.

Calling the binary search function could look like:

vec = c(1.5, 3.5, 5.5, 7.5, 9.5, 11.5, 13.5, 15.5, 17.5, 19.5)
target = 17.5
epsilon = 1.0e-5
idx = bin_search(vec, target, epsilon)

If the return is 0, target not found where the target and corresponding cell value must be within 0.00005 of each other, otherwise, the return value is the index of the first occurrence of the target.