File Explorer

1/**2 * Mnemonist Binary Search Helpers3 * ================================4 *5 * Typical binary search functions.6 */7 8/**9 * Function returning the index of the search value in the array or `-1` if10 * not found.11 *12 * @param  {array} array - Haystack.13 * @param  {any}   value - Needle.14 * @return {number}15 */16exports.search = function(array, value, lo, hi) {17  var mid = 0;18 19  lo = typeof lo !== 'undefined' ? lo : 0;20  hi = typeof hi !== 'undefined' ? hi : array.length;21 22  hi--;23 24  var current;25 26  while (lo <= hi) {27    mid = (lo + hi) >>> 1;28 29    current = array[mid];30 31    if (current > value) {32      hi = ~-mid;33    }34    else if (current < value) {35      lo = -~mid;36    }37    else {38      return mid;39    }40  }41 42  return -1;43};44 45/**46 * Same as above, but can use a custom comparator function.47 *48 * @param  {function} comparator - Custom comparator function.49 * @param  {array}    array      - Haystack.50 * @param  {any}      value      - Needle.51 * @return {number}52 */53exports.searchWithComparator = function(comparator, array, value) {54  var mid = 0,55      lo = 0,56      hi = ~-array.length,57      comparison;58 59  while (lo <= hi) {60    mid = (lo + hi) >>> 1;61 62    comparison = comparator(array[mid], value);63 64    if (comparison > 0) {65      hi = ~-mid;66    }67    else if (comparison < 0) {68      lo = -~mid;69    }70    else {71      return mid;72    }73  }74 75  return -1;76};77 78/**79 * Function returning the lower bound of the given value in the array.80 *81 * @param  {array}  array - Haystack.82 * @param  {any}    value - Needle.83 * @param  {number} [lo] - Start index.84 * @param  {numner} [hi] - End index.85 * @return {number}86 */87exports.lowerBound = function(array, value, lo, hi) {88  var mid = 0;89 90  lo = typeof lo !== 'undefined' ? lo : 0;91  hi = typeof hi !== 'undefined' ? hi : array.length;92 93  while (lo < hi) {94    mid = (lo + hi) >>> 1;95 96    if (value <= array[mid]) {97      hi = mid;98    }99    else {100      lo = -~mid;101    }102  }103 104  return lo;105};106 107/**108 * Same as above, but can use a custom comparator function.109 *110 * @param  {function} comparator - Custom comparator function.111 * @param  {array}    array      - Haystack.112 * @param  {any}      value      - Needle.113 * @return {number}114 */115exports.lowerBoundWithComparator = function(comparator, array, value) {116  var mid = 0,117      lo = 0,118      hi = array.length;119 120  while (lo < hi) {121    mid = (lo + hi) >>> 1;122 123    if (comparator(value, array[mid]) <= 0) {124      hi = mid;125    }126    else {127      lo = -~mid;128    }129  }130 131  return lo;132};133 134/**135 * Same as above, but can work on sorted indices.136 *137 * @param  {array}    array - Haystack.138 * @param  {array}    array - Indices.139 * @param  {any}      value - Needle.140 * @return {number}141 */142exports.lowerBoundIndices = function(array, indices, value, lo, hi) {143  var mid = 0;144 145  lo = typeof lo !== 'undefined' ? lo : 0;146  hi = typeof hi !== 'undefined' ? hi : array.length;147 148  while (lo < hi) {149    mid = (lo + hi) >>> 1;150 151    if (value <= array[indices[mid]]) {152      hi = mid;153    }154    else {155      lo = -~mid;156    }157  }158 159  return lo;160};161 162/**163 * Function returning the upper bound of the given value in the array.164 *165 * @param  {array}  array - Haystack.166 * @param  {any}    value - Needle.167 * @param  {number} [lo] - Start index.168 * @param  {numner} [hi] - End index.169 * @return {number}170 */171exports.upperBound = function(array, value, lo, hi) {172  var mid = 0;173 174  lo = typeof lo !== 'undefined' ? lo : 0;175  hi = typeof hi !== 'undefined' ? hi : array.length;176 177  while (lo < hi) {178    mid = (lo + hi) >>> 1;179 180    if (value >= array[mid]) {181      lo = -~mid;182    }183    else {184      hi = mid;185    }186  }187 188  return lo;189};190 191/**192 * Same as above, but can use a custom comparator function.193 *194 * @param  {function} comparator - Custom comparator function.195 * @param  {array}    array      - Haystack.196 * @param  {any}      value      - Needle.197 * @return {number}198 */199exports.upperBoundWithComparator = function(comparator, array, value) {200  var mid = 0,201      lo = 0,202      hi = array.length;203 204  while (lo < hi) {205    mid = (lo + hi) >>> 1;206 207    if (comparator(value, array[mid]) >= 0) {208      lo = -~mid;209    }210    else {211      hi = mid;212    }213  }214 215  return lo;216};217