findSpan function

dynamic findSpan(
  1. dynamic p,
  2. dynamic u,
  3. dynamic U
)

Implementation

findSpan(p, u, U) {
  var n = U.length - p - 1;

  if (u >= U[n]) {
    return n - 1;
  }

  if (u <= U[p]) {
    return p;
  }

  var low = p;
  var high = n;
  var mid = Math.floor((low + high) / 2);

  while (u < U[mid] || u >= U[mid + 1]) {
    if (u < U[mid]) {
      high = mid;
    } else {
      low = mid;
    }

    mid = Math.floor((low + high) / 2);
  }

  return mid;
}