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