toolkit/modules/BinarySearch.jsm

   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/. */
   4
   5 "use strict";
   6
   7 this.EXPORTED_SYMBOLS = [
   8   "BinarySearch",
   9 ];
  10
  11 this.BinarySearch = Object.freeze({
  12
  13   /**
  14    * Returns the index of the given target in the given array or -1 if the
  15    * target is not found.
  16    *
  17    * See search() for a description of this function's parameters.
  18    *
  19    * @return The index of `target` in `array` or -1 if `target` is not found.
  20    */
  21   indexOf: function (array, target, comparator) {
  22     let [found, idx] = this.search(array, target, comparator);
  23     return found ? idx : -1;
  24   },
  25
  26   /**
  27    * Returns the index within the given array where the given target may be
  28    * inserted to keep the array ordered.
  29    *
  30    * See search() for a description of this function's parameters.
  31    *
  32    * @return The index in `array` where `target` may be inserted to keep `array`
  33    *         ordered.
  34    */
  35   insertionIndexOf: function (array, target, comparator) {
  36     return this.search(array, target, comparator)[1];
  37   },
  38
  39   /**
  40    * Searches for the given target in the given array.
  41    *
  42    * @param  array
  43    *         An array whose elements are ordered by `comparator`.
  44    * @param  target
  45    *         The value to search for.
  46    * @param  comparator
  47    *         A function that takes two arguments and compares them, returning a
  48    *         negative number if the first should be ordered before the second,
  49    *         zero if the first and second have the same ordering, or a positive
  50    *         number if the second should be ordered before the first.  The first
  51    *         argument is always `target`, and the second argument is a value
  52    *         from the array.
  53    * @return An array with two elements.  If `target` is found, the first
  54    *         element is true, and the second element is its index in the array.
  55    *         If `target` is not found, the first element is false, and the
  56    *         second element is the index where it may be inserted to keep the
  57    *         array ordered.
  58    */
  59   search: function (array, target, comparator) {
  60     let low = 0;
  61     let high = array.length - 1;
  62     while (low <= high) {
  63       let mid = Math.floor((low + high) / 2);
  64       let cmp = comparator(target, array[mid]);
  65       if (cmp == 0)
  66         return [true, mid];
  67       if (cmp < 0)
  68         high = mid - 1;
  69       else
  70         low = mid + 1;
  71     }
  72     return [false, low];
  73   },
  74 });