toolkit/modules/BinarySearch.sys.mjs

   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 export var BinarySearch = Object.freeze({
   6   /**
   7    * Returns the index of the given target in the given array or -1 if the
   8    * target is not found.
   9    *
  10    * See search() for a description of this function's parameters.
  11    *
  12    * @return The index of `target` in `array` or -1 if `target` is not found.
  13    */
  14   indexOf(comparator, array, target) {
  15     let [found, idx] = this.search(comparator, array, target);
  16     return found ? idx : -1;
  17   },
  18
  19   /**
  20    * Returns the index within the given array where the given target may be
  21    * inserted to keep the array ordered.
  22    *
  23    * See search() for a description of this function's parameters.
  24    *
  25    * @return The index in `array` where `target` may be inserted to keep `array`
  26    *         ordered.
  27    */
  28   insertionIndexOf(comparator, array, target) {
  29     return this.search(comparator, array, target)[1];
  30   },
  31
  32   /**
  33    * Searches for the given target in the given array.
  34    *
  35    * @param  comparator
  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
  41    *         from the array.
  42    * @param  array
  43    *         An array whose elements are ordered by `comparator`.
  44    * @param  target
  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
  50    *         array ordered.
  51    */
  52   search(comparator, array, target) {
  53     let low = 0;
  54     let high = array.length - 1;
  55     while (low <= high) {
  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]);
  59       if (cmp == 0) {
  60         return [true, mid];
  61       }
  62       if (cmp < 0) {
  63         high = mid - 1;
  64       } else {
  65         low = mid + 1;
  66       }
  67     }
  68     return [false, low];
  69   },
  70 });