Skip to content

Instantly share code, notes, and snippets.

@mgiuffrida
Created December 17, 2016 23:47
Show Gist options
  • Save mgiuffrida/944d41782a63979c103a4a3bbdbd04a9 to your computer and use it in GitHub Desktop.
Save mgiuffrida/944d41782a63979c103a4a3bbdbd04a9 to your computer and use it in GitHub Desktop.
Approximate binary search
/**
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment