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
69
70
71
72
73
74
|
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this file,
* You can obtain one at http://mozilla.org/MPL/2.0/. */
"use strict";
var EXPORTED_SYMBOLS = ["BinarySearch"];
var BinarySearch = Object.freeze({
/**
* Returns the index of the given target in the given array or -1 if the
* target is not found.
*
* See search() for a description of this function's parameters.
*
* @return The index of `target` in `array` or -1 if `target` is not found.
*/
indexOf(comparator, array, target) {
let [found, idx] = this.search(comparator, array, target);
return found ? idx : -1;
},
/**
* Returns the index within the given array where the given target may be
* inserted to keep the array ordered.
*
* See search() for a description of this function's parameters.
*
* @return The index in `array` where `target` may be inserted to keep `array`
* ordered.
*/
insertionIndexOf(comparator, array, target) {
return this.search(comparator, array, target)[1];
},
/**
* Searches for the given target in the given array.
*
* @param comparator
* A function that takes two arguments and compares them, returning a
* negative number if the first should be ordered before the second,
* zero if the first and second have the same ordering, or a positive
* number if the second should be ordered before the first. The first
* argument is always `target`, and the second argument is a value
* from the array.
* @param array
* An array whose elements are ordered by `comparator`.
* @param target
* The value to search for.
* @return An array with two elements. If `target` is found, the first
* element is true, and the second element is its index in the array.
* If `target` is not found, the first element is false, and the
* second element is the index where it may be inserted to keep the
* array ordered.
*/
search(comparator, array, target) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
// Thanks to http://jsperf.com/code-review-1480 for this tip.
let mid = (low + high) >> 1;
let cmp = comparator(target, array[mid]);
if (cmp == 0) {
return [true, mid];
}
if (cmp < 0) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return [false, low];
},
});
|
