Approximate binary search

binary-search-approx.js

/**
 * Returns the index of the item in a sorted array closest to |target|.
 * @param {!Array<number>} arr Sorted array (ascending or descending).
 * @param {number} target
 * @return {number} Index of closest item, or -1 on error.
 */
function binarySearchApprox(arr, value) {
  if (!arr.length || !Number.isFinite(value)) return -1;
  if (arr.length == 1) return 0;

  var minIndex = 0;
  var maxIndex = arr.length - 1;
  var isAscending = arr[maxIndex] > arr[minIndex];

  while (maxIndex - minIndex > 1) {
    // Binary search.
    var curIndex = (maxIndex + minIndex) >> 1;
    if (arr[curIndex] == value)
      return curIndex;
    if (arr[curIndex] > value == isAscending)
      maxIndex = curIndex;
    else
      minIndex = curIndex;
  }
  if (Math.abs(value - arr[minIndex]) < Math.abs(value - arr[maxIndex]))
    return minIndex;
  return maxIndex;
}