1 /*
  2  * SearchUtils.js - Misc search utility routines
  3  *
  4  * Copyright © 2013-2015, JEDLSoft
  5  *
  6  * Licensed under the Apache License, Version 2.0 (the "License");
  7  * you may not use this file except in compliance with the License.
  8  * You may obtain a copy of the License at
  9  *
 10  *     http://www.apache.org/licenses/LICENSE-2.0
 11  *
 12  * Unless required by applicable law or agreed to in writing, software
 13  * distributed under the License is distributed on an "AS IS" BASIS,
 14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 15  *
 16  * See the License for the specific language governing permissions and
 17  * limitations under the License.
 18  */
 19 
 20 var SearchUtils = {};
 21 
 22 /**
 23  * Binary search a sorted array for a particular target value.
 24  * If the exact value is not found, it returns the index of the smallest
 25  * entry that is greater than the given target value.<p>
 26  *
 27  * The comparator
 28  * parameter is a function that knows how to compare elements of the
 29  * array and the target. The function should return a value greater than 0
 30  * if the array element is greater than the target, a value less than 0 if
 31  * the array element is less than the target, and 0 if the array element
 32  * and the target are equivalent.<p>
 33  *
 34  * If the comparator function is not specified, this function assumes
 35  * the array and the target are numeric values and should be compared
 36  * as such.<p>
 37  *
 38  *
 39  * @static
 40  * @param {*} target element being sought
 41  * @param {Array} arr the array being searched
 42  * @param {?function(*,*)=} comparator a comparator that is appropriate for comparing two entries
 43  * in the array
 44  * @return the index of the array into which the value would fit if
 45  * inserted, or -1 if given array is not an array or the target is not
 46  * a number
 47  */
 48 SearchUtils.bsearch = function(target, arr, comparator) {
 49     if (typeof(arr) === 'undefined' || !arr || typeof(target) === 'undefined') {
 50         return -1;
 51     }
 52 
 53     var high = arr.length - 1,
 54         low = 0,
 55         mid = 0,
 56         value,
 57         cmp = comparator || SearchUtils.bsearch.numbers;
 58 
 59     while (low <= high) {
 60         mid = Math.floor((high+low)/2);
 61         value = cmp(arr[mid], target);
 62         if (value > 0) {
 63             high = mid - 1;
 64         } else if (value < 0) {
 65             low = mid + 1;
 66         } else {
 67             return mid;
 68         }
 69     }
 70 
 71     return low;
 72 };
 73 
 74 /**
 75  * Returns whether or not the given element is greater than, less than,
 76  * or equal to the given target.<p>
 77  *
 78  * @private
 79  * @static
 80  * @param {number} element the element being tested
 81  * @param {number} target the target being sought
 82  */
 83 SearchUtils.bsearch.numbers = function(element, target) {
 84     return element - target;
 85 };
 86 
 87 /**
 88  * Do a bisection search of a function for a particular target value.<p>
 89  *
 90  * The function to search is a function that takes a numeric parameter,
 91  * does calculations, and returns gives a numeric result. The
 92  * function should should be smooth and not have any discontinuities
 93  * between the low and high values of the parameter.
 94  *
 95  *
 96  * @static
 97  * @param {number} target value being sought
 98  * @param {number} low the lower bounds to start searching
 99  * @param {number} high the upper bounds to start searching
100  * @param {number} precision minimum precision to support. Use 0 if you want to use the default.
101  * @param {?function(number)=} func function to search
102  * @return an approximation of the input value to the function that gives the desired
103  * target output value, correct to within the error range of Javascript floating point
104  * arithmetic, or NaN if there was some error
105  */
106 SearchUtils.bisectionSearch = function(target, low, high, precision, func) {
107     if (typeof(target) !== 'number' ||
108             typeof(low) !== 'number' ||
109             typeof(high) !== 'number' ||
110             typeof(func) !== 'function') {
111         return NaN;
112     }
113 
114     var mid = 0,
115         value,
116         pre = precision > 0 ? precision : 1e-13;
117 
118     do {
119         mid = (high+low)/2;
120         value = func(mid);
121         if (value > target) {
122             high = mid;
123         } else if (value < target) {
124             low = mid;
125         }
126     } while (high - low > pre);
127 
128     return mid;
129 };
130 
131 module.exports = SearchUtils;
132