You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
43 lines
1.4 KiB
43 lines
1.4 KiB
3 years ago
|
var baseSortedIndexBy = require('./_baseSortedIndexBy'),
|
||
|
|
identity = require('./identity'),
|
||
|
|
isSymbol = require('./isSymbol');
|
||
|
|
|
||
|
|
/** Used as references for the maximum length and index of an array. */
|
||
|
|
var MAX_ARRAY_LENGTH = 4294967295,
|
||
|
|
HALF_MAX_ARRAY_LENGTH = MAX_ARRAY_LENGTH >>> 1;
|
||
|
|
|
||
|
|
/**
|
||
|
|
* The base implementation of `_.sortedIndex` and `_.sortedLastIndex` which
|
||
|
|
* performs a binary search of `array` to determine the index at which `value`
|
||
|
|
* should be inserted into `array` in order to maintain its sort order.
|
||
|
|
*
|
||
|
|
* @private
|
||
|
|
* @param {Array} array The sorted array to inspect.
|
||
|
|
* @param {*} value The value to evaluate.
|
||
|
|
* @param {boolean} [retHighest] Specify returning the highest qualified index.
|
||
|
|
* @returns {number} Returns the index at which `value` should be inserted
|
||
|
|
* into `array`.
|
||
|
|
*/
|
||
|
|
function baseSortedIndex(array, value, retHighest) {
|
||
|
|
var low = 0,
|
||
|
|
high = array == null ? low : array.length;
|
||
|
|
|
||
|
|
if (typeof value == 'number' && value === value && high <= HALF_MAX_ARRAY_LENGTH) {
|
||
|
|
while (low < high) {
|
||
|
|
var mid = (low + high) >>> 1,
|
||
|
|
computed = array[mid];
|
||
|
|
|
||
|
|
if (computed !== null && !isSymbol(computed) &&
|
||
|
|
(retHighest ? (computed <= value) : (computed < value))) {
|
||
|
|
low = mid + 1;
|
||
|
|
} else {
|
||
|
|
high = mid;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return high;
|
||
|
|
}
|
||
|
|
return baseSortedIndexBy(array, value, identity, retHighest);
|
||
|
|
}
|
||
|
|
|
||
|
|
module.exports = baseSortedIndex;
|