function binarySearch_(arr, compareFn, isEvaluator, opt_target, opt_selfObj) {
  let left = 0;            // inclusive
  let right = arr.length;  // exclusive
  let found;
  while (left < right) {
    const middle = left + ((right - left) >>> 1);
    let compareResult;
    if (isEvaluator) {
      compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr);
    } else {
      // NOTE(dimvar): To avoid this cast, we'd have to use function overloading
      // for the type of binarySearch_, which the type system can't express yet.
      compareResult = /** @type {function(?, ?): number} */ (compareFn)(
          opt_target, arr[middle]);
    }
    if (compareResult > 0) {
      left = middle + 1;
    } else {
      right = middle;
      // We are looking for the lowest index so we can't return immediately.
      found = !compareResult;
    }
  }
  // left is the index if found, or the insertion point otherwise.
  // Avoiding bitwise not operator, as that causes a loss in precision for array
  // indexes outside the bounds of a 32-bit signed integer.  Array indexes have
  // a maximum value of 2^32-2 https://tc39.es/ecma262/#array-index
  return found ? left : -left - 1;
}
Implementation of a binary search algorithm which knows how to use both
comparison functions and evaluators. If an evaluator is provided, will call
the evaluator with the given optional data object, conforming to the
interface defined in binarySelect. Otherwise, if a comparison function is
provided, will call the comparison function against the given data object.

This implementation purposefully does not use goog.bind or goog.partial for
performance reasons.

Runtime: O(log n)

@param {IArrayLike<?>} arr The array to be searched.
@param {function(?, ?, ?): number | function(?, ?): number} compareFn
    Either an evaluator or a comparison function, as defined by binarySearch
    and binarySelect above.
@param {boolean} isEvaluator Whether the function is an evaluator or a
    comparison function.
@param {?=} opt_target If the function is a comparison function, then
    this is the target to binary search for.
@param {Object=} opt_selfObj If the function is an evaluator, this is an
    optional this object for the evaluator.
@return {number} Lowest index of the target value if found, otherwise
    (-(insertion point) - 1). The insertion point is where the value should
    be inserted into arr to preserve the sorted property.  Return value >= 0
    iff target is found.
@private