1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
3 * You can obtain one at http://mozilla.org/MPL/2.0/. */
5 export var BinarySearch = Object.freeze({
7 * Returns the index of the given target in the given array or -1 if the
10 * See search() for a description of this function's parameters.
12 * @return The index of `target` in `array` or -1 if `target` is not found.
14 indexOf(comparator, array, target) {
15 let [found, idx] = this.search(comparator, array, target);
16 return found ? idx : -1;
20 * Returns the index within the given array where the given target may be
21 * inserted to keep the array ordered.
23 * See search() for a description of this function's parameters.
25 * @return The index in `array` where `target` may be inserted to keep `array`
28 insertionIndexOf(comparator, array, target) {
29 return this.search(comparator, array, target)[1];
33 * Searches for the given target in the given array.
36 * A function that takes two arguments and compares them, returning a
37 * negative number if the first should be ordered before the second,
38 * zero if the first and second have the same ordering, or a positive
39 * number if the second should be ordered before the first. The first
40 * argument is always `target`, and the second argument is a value
43 * An array whose elements are ordered by `comparator`.
45 * The value to search for.
46 * @return An array with two elements. If `target` is found, the first
47 * element is true, and the second element is its index in the array.
48 * If `target` is not found, the first element is false, and the
49 * second element is the index where it may be inserted to keep the
52 search(comparator, array, target) {
54 let high = array.length - 1;
56 // Thanks to http://jsperf.com/code-review-1480 for this tip.
57 let mid = (low + high) >> 1;
58 let cmp = comparator(target, array[mid]);