Source: Core/binarySearch.js

  1. /*global define*/
  2. define([
  3.         './defined',
  4.         './DeveloperError'
  5.     ], function(
  6.         defined,
  7.         DeveloperError) {
  8.     'use strict';
  10.     /**
  11.      * Finds an item in a sorted array.
  12.      *
  13.      * @exports binarySearch
  14.      *
  15.      * @param {Array} array The sorted array to search.
  16.      * @param {Object} itemToFind The item to find in the array.
  17.      * @param {binarySearch~Comparator} comparator The function to use to compare the item to
  18.      *        elements in the array.
  19.      * @returns {Number} The index of <code>itemToFind</code> in the array, if it exists.  If <code>itemToFind</code>
  20.      *        does not exist, the return value is a negative number which is the bitwise complement (~)
  21.      *        of the index before which the itemToFind should be inserted in order to maintain the
  22.      *        sorted order of the array.
  23.      *
  24.      * @example
  25.      * // Create a comparator function to search through an array of numbers.
  26.      * function comparator(a, b) {
  27.      *     return a - b;
  28.      * };
  29.      * var numbers = [0, 2, 4, 6, 8];
  30.      * var index = Cesium.binarySearch(numbers, 6, comparator); // 3
  31.      */
  32.     function binarySearch(array, itemToFind, comparator) {
  33.         //>>includeStart('debug', pragmas.debug);
  34.         if (!defined(array)) {
  35.             throw new DeveloperError('array is required.');
  36.         }
  37.         if (!defined(itemToFind)) {
  38.             throw new DeveloperError('itemToFind is required.');
  39.         }
  40.         if (!defined(comparator)) {
  41.             throw new DeveloperError('comparator is required.');
  42.         }
  43.         //>>includeEnd('debug');
  45.         var low = 0;
  46.         var high = array.length - 1;
  47.         var i;
  48.         var comparison;
  50.         while (low <= high) {
  51.             i = ~~((low + high) / 2);
  52.             comparison = comparator(array[i], itemToFind);
  53.             if (comparison < 0) {
  54.                 low = i + 1;
  55.                 continue;
  56.             }
  57.             if (comparison > 0) {
  58.                 high = i - 1;
  59.                 continue;
  60.             }
  61.             return i;
  62.         }
  63.         return ~(high + 1);
  64.     }
  66.     /**
  67.      * A function used to compare two items while performing a binary search.
  68.      * @callback binarySearch~Comparator
  69.      *
  70.      * @param {Object} a An item in the array.
  71.      * @param {Object} b The item being searched for.
  72.      * @returns {Number} Returns a negative value if <code>a</code> is less than <code>b</code>,
  73.      *          a positive value if <code>a</code> is greater than <code>b</code>, or
  74.      *          0 if <code>a</code> is equal to <code>b</code>.
  75.      *
  76.      * @example
  77.      * function compareNumbers(a, b) {
  78.      *     return a - b;
  79.      * }
  80.      */
  82.     return binarySearch;
  83. });