My lecturer gives me this syntax to perform a binary search

BS = function(array, x, eps) {
 
  lo <- 1; n <- length(array)

  while (lo <= n) {

    mid <- as.integer(round((lo   n) / 2))

    if (abs(array[mid] - x) <= eps) {

      return(mid)

    } else if (array[mid] < x) { 

      lo <- mid   1

    } else {

      n <- mid - 1
    }
  }
  return(0)
}

while I have a good guess on what the code do, I can't wrap my head around the eps variable, and trying to change it into different value to see what difference it makes doesn't explain it either, can someone please kindly explain what it does?

CodePudding user response：

In this binary search function, eps denotes the termination condition. When the following condition is met

abs(array[mid] - x) <= eps

the code knows that the searching objective array[mid] is close to x (within the tolerance eps), then we return mid as the termination of searching.

CodePudding user response：

The acronym eps stands for epsilon of the machine, and it denotes the fault tolerance in BS.