Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | 491718x 491717x 491716x 491715x 491715x 491715x 1996835x 1996835x 1996835x 232649x 232649x 1764186x 1759357x 1759357x 4829x 486886x | import Check from "./Check.js";
/**
* Finds an item in a sorted array.
*
* @function
* @param {Array|Int8Array|Uint8Array|Int16Array|Uint16Array|Int32Array|Uint32Array|Float32Array|Float64Array} array The sorted array to search.
* @param {*} itemToFind The item to find in the array.
* @param {binarySearchComparator} comparator The function to use to compare the item to
* elements in the array.
* @returns {number} The index of <code>itemToFind</code> in the array, if it exists. If <code>itemToFind</code>
* does not exist, the return value is a negative number which is the bitwise complement (~)
* of the index before which the itemToFind should be inserted in order to maintain the
* sorted order of the array.
*
* @example
* // Create a comparator function to search through an array of numbers.
* function comparator(a, b) {
* return a - b;
* };
* const numbers = [0, 2, 4, 6, 8];
* const index = Cesium.binarySearch(numbers, 6, comparator); // 3
*/
function binarySearch(array, itemToFind, comparator) {
//>>includeStart('debug', pragmas.debug);
Check.defined("array", array);
Check.defined("itemToFind", itemToFind);
Check.defined("comparator", comparator);
//>>includeEnd('debug');
let low = 0;
let high = array.length - 1;
let i;
let comparison;
while (low <= high) {
i = ~~((low + high) / 2);
comparison = comparator(array[i], itemToFind);
if (comparison < 0) {
low = i + 1;
continue;
}
if (comparison > 0) {
high = i - 1;
continue;
}
return i;
}
return ~(high + 1);
}
/**
* A function used to compare two items while performing a binary search.
* @callback binarySearchComparator
*
* @param {*} a An item in the array.
* @param {*} b The item being searched for.
* @returns {number} Returns a negative value if <code>a</code> is less than <code>b</code>,
* a positive value if <code>a</code> is greater than <code>b</code>, or
* 0 if <code>a</code> is equal to <code>b</code>.
*
* @example
* function compareNumbers(a, b) {
* return a - b;
* }
*/
export default binarySearch;
|