This article looks at the sorted family of methods that determine the index to insert a value into a sorted array. Including sortedIndex, sortedLastIndex, sortedIndexOf, sortedLastIndexOf, sortedIndexBy, sortedLastIndexBy, sortedUniq, sortedUniqBy and core Heart methods baseSortedIndex, baseSortedIndexBy, baseSortedUniq.

We’ll start with an example of binary lookup, the algorithm at the heart of the sortedIndex series of methods. Incidentally, analyze the dependent Lodash method eq.

The specific dependency path diagram is as follows:

Binary search

Binary Search is a Search algorithm used to find a specified element in an array. Note that this array needs to be an ordered array to be valid, and the time complexity is O(log2n). Here is a comparison of binary search versus linear search.

The most common binary search

Here are the most common JS implementations of binary lookup:

function binarySearch(array, value) {
  let low = 0; // The minimum index of the array
  let high = array.length - 1; // The maximum index of the array
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (value == array[mid]) {
      // value is equal to the intermediate value
      return mid;
    } else if (array[mid] < value) {
      // If value is greater than the median value, move low
      low = mid + 1;
    } else if (value < array[mid]) {
      // Value is less than the middle value, move high
      high = mid - 1; }}}Copy the code

Calculate according to the data given by the sample graph:

const array = [1.3.5.7.11.13.17.19.23.29.31.37.41.43.47.53.59];
binarySearch(array, 37);
Copy the code
The iteration low high mid array[mid]
1 0 16 8 23
2 9 16 12 41
3 9 11 10 31
4 11 11 11 37

However, this algorithm has some problems in some cases. When there are multiple duplicate values in the array, it can only find one of them, but not the leftmost or rightmost one. At that time, the sorted algorithm needed this ability, so it needed to evolve!

The binary algorithm looks for the left edge

Let’s start with the code to find the left edge:

function binarySearchLeft(array, value) {
  let low = 0;
  let high = array.length; / / the difference between 1
  while (low < high) {
    / / the difference between 2
    let mid = Math.floor((low + high) / 2);
    if (value == array[mid]) {
      high = mid; / / the difference between 3
    } else if (array[mid] < value) {
      low = mid + 1;
    } else if (value < array[mid]) {
      high = mid; / / the difference between 4}}return low;
}
Copy the code

The difference with ordinary binary algorithm is the following:

  1. The initialhighTo give isarray.length, there is noMinus 1.
  2. The judgment condition is<Rather than< =.
  3. whenvalue == array[mid]Does not return immediatelymid“, but keep looking to the left.
  4. whenvalue < array[mid]When,high = midRather thanhigh = mid - 1.

1 and 4 are the same reason that we don’t need to subtract 1 because the judgment condition in 2 becomes < instead of <=. If you find a mid equal to value, do not immediately return. Instead, set it to high and continue to look left until you find the leftmost position.

Some students may ask why not just change the third clause and continue to use the <= version. This is because if the value is greater than all of the values in the array, low will be greater than the maximum index, resulting in an out-of-bounds.

The binary algorithm looks for the right-hand boundary

Continue to release the code to find the right edge:

function binarySearchRight(array, value) {
  let low = 0;
  let high = array.length; / / the difference between 1
  while (low < high) {
    / / the difference between 2
    let mid = Math.floor((low + high) / 2);
    if (value == array[mid]) {
      low = mid + 1; / / the difference between 3
    } else if (array[mid] < value) {
      low = mid + 1;
    } else if (value < array[mid]) {
      high = mid; / / the difference between 4}}return low;
}
Copy the code

It’s the same thing as finding the right edge, except the difference is low = mid + 1.

Dependent built-in methods

The core built-in methods of both dependencies are variations of the binary search algorithm.

baseSortedIndex

import baseSortedIndexBy from './baseSortedIndexBy.js';
import isSymbol from '.. /isSymbol.js';

/** used as a reference to the maximum length and array index */
// 4294967295 == 0xFFFFFFFF, 8 bytes, 64 bits
const MAX_ARRAY_LENGTH = 4294967295;
// 4294967295 >>> 1 = 2147483647 === 0x7fffff,
// The logical shift is 1 bit to the right
const HALF_MAX_ARRAY_LENGTH = MAX_ARRAY_LENGTH >>> 1;

/** * the basic implementation of 'sortedIndex' and 'sortedLastIndex', performs binary search on 'array', * determines which index 'value' should be inserted into 'array', ensuring that the original array order is not messed up **@private
 * @param {Array} Array The sorted array to check@param {*} Value Specifies the value to be calculated *@param {boolean} Whether the [retHighest] flag returns the maximum matching index *@returns {number} Return 'value' where 'index' */ 'should be inserted into' array '
function baseSortedIndex(array, value, retHighest) {
  // Initialize variables
  let low = 0;
  // If array is empty, high is 0; otherwise, length is 0
  let high = array == null ? low : array.length;

  // When value is of type number
  if (
    typeof value === 'number' &&
    value === value &&
    high <= HALF_MAX_ARRAY_LENGTH
  ) {
    // loop when low < high
    while (low < high) {
      // Move logic one bit to the right and half the size
      const mid = (low + high) >>> 1;
      // Computed is the middle variable
      const computed = array[mid];
      // If the intermediate variable is less than value, go to the lower half of the range
      if( computed ! = =null &&
        !isSymbol(computed) &&
        (retHighest ? computed <= value : computed < value)
      ) {
        low = mid + 1;
      } else {
        // If the intermediate variable is greater than or equal to value, go to the first half of the rangehigh = mid; }}// Return high if low>=high
    return high;
  }
  BaseSortedIndexBy is called and returned if it is not a numeric type, not null, or if the numeric value exceeds HALF_MAX_ARRAY_LENGTH
  return baseSortedIndexBy(array, value, (value) = > value, retHighest);
}

export default baseSortedIndex;
Copy the code

baseSortedIndexBy

import isSymbol from '.. /isSymbol.js';

/** used as a reference to the maximum length and array index */
// 4294967295 == 0xFFFFFFFF, 8 bytes, 64 bits
const MAX_ARRAY_LENGTH = 4294967295;
// 4294967295 == 0xfffffffe
const MAX_ARRAY_INDEX = MAX_ARRAY_LENGTH - 1;

/** * the basic implementation of the sortedIndexBy and sortedLastIndexBy methods, * calculates the index of value in a sorted array by calling 'iteratee' for each element of array and comparing it with 'value'. * 'iteratee' calls one argument (' value ') * *@private
 * @param {Array} Array Sorted array * to check@param {*} Value Specifies the value to be calculated *@param {Function} Iteratee The iteratee * called by each element@param {boolean} Whether the [retHighest] flag returns the maximum matching index *@returns {number} Return 'value' where 'index' */ 'should be inserted into' array '
function baseSortedIndexBy(array, value, iteratee, retHighest) {
  // Initialize the variable low, high
  let low = 0;
  let high = array == null ? 0 : array.length;
  if (high == 0) {
    return 0;
  }

  // Iteratee the value
  value = iteratee(value);

  // Only NaN! == NaN satisfies value! = = value is true
  constvalIsNaN = value ! == value;// Whether it is not null
  const valIsNull = value === null;
  // is the symbol
  const valIsSymbol = isSymbol(value);
  // Whether it is undefined
  const valIsUndefined = value === undefined;

  // Binary search
  while (low < high) {
    let setLow;
    const mid = Math.floor((low + high) / 2);
    // Use iteratee to compute the median value
    const computed = iteratee(array[mid]);
    // Whether it is defined
    constothIsDefined = computed ! = =undefined;
    // Whether the value is null
    const othIsNull = computed === null;
    // is equal to itself
    const othIsReflexive = computed === computed;
    // is the symbol
    const othIsSymbol = isSymbol(computed);

    // These are all comparison processes that simple size comparisons cannot solve
    if (valIsNaN) {
      setLow = retHighest || othIsReflexive;
    } else if (valIsUndefined) {
      setLow = othIsReflexive && (retHighest || othIsDefined);
    } else if(valIsNull) { setLow = othIsReflexive && othIsDefined && (retHighest || ! othIsNull); }else if(valIsSymbol) { setLow = othIsReflexive && othIsDefined && ! othIsNull && (retHighest || ! othIsSymbol); }else if (othIsNull || othIsSymbol) {
      setLow = false;
    } else {
      // This is the most general processing, above are handling special cases
      // If you look at it from left to right, <=
      setLow = retHighest ? computed <= value : computed < value;
    }
    // Binary search core
    if (setLow) {
      // If the value is greater than the median value, change the value to low
      low = mid + 1;
    } else {
      // If the value is less than the median value, change the value to highhigh = mid; }}return Math.min(high, MAX_ARRAY_INDEX);
}

export default baseSortedIndexBy;
Copy the code

baseSortedUniq

import eq from '.. /eq.js';

/** ** 'sortedUniq' and 'sortedUniqBy' base implementation **@private
 * @param {Array} Array Array to check *@param {Function} [iteratee] 'iteratee' calls each element *@returns {Array} Returns a new array copy */
function baseSortedUniq(array, iteratee) {
  / / initialization
  let seen;
  let index = -1;
  let resIndex = 0;

  // Get the length of the array
  const { length } = array;
  const result = [];

  / / iteration
  while (++index < length) {
    // Value is each element, computed is the converted element
    const value = array[index],
      computed = iteratee ? iteratee(value) : value;
    // If index is 0 or computed! == seen
    // Seen is actually computed last time
    if(! index || ! eq(computed, seen)) {// Put computed in seen
      seen = computed;
      // Only elements that do not repeat the previous element are placed in result
      result[resIndex++] = value === 0 ? 0: value; }}return result;
}

export default baseSortedUniq;
Copy the code

Dependent lodash methods

eq

/** * Performs * [' SameValueZero '](http://ecma-international.org/ecma-262/7.0/#sec-samevaluezero) comparison between two values ** to determine if two values are equal **@since 4.0.0
 * @category Lang
 * @param {*} Value Specifies the value to be compared *@param {*} Other The other value * to compare@returns {boolean} Return 'true' if two values are equal, false * otherwise@example
 *
 * const object = { 'a': 1 }
 * const other = { 'a': 1 }
 *
 * eq(object, object)
 * // => true
 *
 * eq(object, other)
 * // => false
 *
 * eq('a', 'a')
 * // => true
 *
 * eq('a', Object('a'))
 * // => false
 *
 * eq(NaN, NaN)
 * // => true
 */
function eq(value, other) {
  // True is returned only if values are strictly equal or if both values are null
  // Return false for all others
  returnvalue === other || (value ! == value && other ! == other); }export default eq;
Copy the code

The family of sorted

The following is a breakdown of the six sorted family methods.

sortedIndex

import baseSortedIndex from './.internal/baseSortedIndex.js';

/** * Uses binary retrieval to determine the minimum index position that should be inserted into the array 'value' to ensure array sorting. * *@since 0.1.0 from *@category Array
 * @param {Array} Array Sorted array to check. *@param {*} Value Specifies the value to be calculated *@returns {number} Return 'value' the position 'index' that should be inserted into 'array'. *@example
 *
 * sortedIndex([30, 50], 40)
 * // => 1
 */
function sortedIndex(array, value) {
  BaseSortedIndex (array, value, false)
  return baseSortedIndex(array, value);
}

export default sortedIndex;
Copy the code

sortedLastIndex

import baseSortedIndex from './.internal/baseSortedIndex.js';

/** ** This method is similar to 'sortedIndex' but returns' value 'as the largest possible index position' index 'in' array '. * *@since 3.0.0
 * @category Array
 * @param {Array} Array Sorted array to check. *@param {*} Value Specifies the value to be calculated *@returns {number} Return 'value' the position 'index' that should be inserted into 'array'. * into `array`. *@example
 *
 * sortedLastIndex([4, 5, 5, 5, 6], 5)
 * // => 4
 */
function sortedLastIndex(array, value) {
  // Call baseSortedIndex(array, value, true)
  return baseSortedIndex(array, value, true);
}

export default sortedLastIndex;
Copy the code

sortedIndexOf

import baseSortedIndex from './.internal/baseSortedIndex.js';
import eq from './eq.js';

/** * This method is similar to 'indexOf', but it performs binary retrieval on an already sorted array 'array'. * *@since 4.0.0
 * @category Array
 * @param {Array} Array Array to check *@param {*} Value Indicates the value to be searched *@returns {number} Returns index of the matching value, or -1 * otherwise@example
 *
 * sortedIndexOf([4, 5, 5, 5, 6], 5)
 * // => 1
 */
function sortedIndexOf(array, value) {
  // Get the length of the array
  const length = array == null ? 0 : array.length;
  // If the array has content, process it
  if (length) {
    // Same as sortedIndex
    const index = baseSortedIndex(array, value);
    // The value of the array is equal to the value of the array
    // If the value is not equal, it does not exist in the array
    if (index < length && eq(array[index], value)) {
      // Make sure to find the value in the array, return index
      returnindex; }}// Return -1 if the array has no content
  return -1;
}

export default sortedIndexOf;
Copy the code

sortedLastIndexOf

import baseSortedIndex from './.internal/baseSortedIndex.js';
import eq from './eq.js';

/** * This method is similar to 'lastIndexOf', but it performs binary retrieval on an already sorted array. * *@since 4.0.0
 * @category Array
 * @param {Array} Array Array to check *@param {*} Value Indicates the value to be searched *@returns {number} Returns index of the matching value, or -1 * otherwise@example
 *
 * sortedLastIndexOf([4, 5, 5, 5, 6], 5)
 * // => 3
 */
function sortedLastIndexOf(array, value) {
  // Get the length of the array
  const length = array == null ? 0 : array.length;
  if (length) {
    // Same as sortedLastIndex, but minus 1
    const index = baseSortedIndex(array, value, true) - 1;
    // If the value is not equal, it does not exist in the array
    if (eq(array[index], value)) {
      // Make sure to find the value in the array, return index
      returnindex; }}return -1;
}

export default sortedLastIndexOf;
Copy the code

sortedIndexBy

import baseSortedIndexBy from './.internal/baseSortedIndexBy.js';

/** * This method is similar to 'sortedIndex', but it takes an 'iteratee' that calls each element of 'array' and returns the result compared to 'value' to calculate the sort. * iteratee takes one argument :(value). * *@since 4.0.0
 * @category Array
 * @param {Array} Array Sorted array to check. *@param {*} Value Specifies the value to be calculated *@param {Function} Iteratee The iteratee iteration function called for each element *@returns {number} Return 'value' which index 'index' should be inserted into 'array'. *@example
 *
 * const objects = [{ 'n': 4 }, { 'n': 5 }]
 *
 * sortedIndexBy(objects, { 'n': 4 }, ({ n }) => n)
 * // => 0
 */
function sortedIndexBy(array, value, iteratee) {
  // Call the core method baseSortedIndexBy(array, Value, iteratee)
  return baseSortedIndexBy(array, value, iteratee);
}

export default sortedIndexBy;
Copy the code

sortedLastIndexBy

import baseSortedIndexBy from './.internal/baseSortedIndexBy.js';

/** * This method is similar to 'sortedLastIndex', but it takes an 'iteratee' that calls each element of 'array' and returns the result compared to 'value' to calculate the sort. * iteratee takes one argument :(value). * *@since 4.0.0
 * @category Array
 * @param {Array} Array Sorted array to check. *@param {*} Value Specifies the value to be calculated *@param {Function} Iteratee The iteratee iteration function called for each element *@returns {number} Return 'value' which index 'index' should be inserted into 'array'. *@example
 *
 * const objects = [{ 'n': 4 }, { 'n': 5 }]
 *
 * sortedLastIndexBy(objects, { 'n': 4 }, ({ n }) => n)
 * // => 1
 */
function sortedLastIndexBy(array, value, iteratee) {
  return baseSortedIndexBy(array, value, iteratee, true);
}

export default sortedLastIndexBy;
Copy the code

sortedUniq

import baseSortedUniq from './.internal/baseSortedUniq.js';

/** * This method is similar to 'uniq', but it only works on sorted arrays. * If the input array is determined to be sorted, 'sortedUniq' is faster than 'uniq'. * *@since 4.0.0
 * @category Array
 * @param {Array} Array Array to check *@returns {Array} Returns a new array copy *@example
 *
 * sortedUniq([1, 1, 2])
 * // => [1, 2]
 */
function sortedUniq(array) {
  // When array ==null or length 0, return []
  returnarray ! =null && array.length
    ? // Otherwise call baseSortedUniq
      baseSortedUniq(array)
    : [];
}

export default sortedUniq;
Copy the code

sortedUniqBy

import baseSortedUniq from './.internal/baseSortedUniq.js';

/** * This method is similar to 'uniqBy', but it optimizes the speed of sorted arrays. * *@since 4.0.0
 * @category Array
 * @param {Array} Array Array to check *@param {Function} Iteratee The iteratee iteration function called for each element *@returns {Array} Returns a new array copy *@example* * sortedUniqBy ([1.1, 1.2, 2.3, 2.4], Math. The floor) * / / = > [1.1, 2.3] * /
function sortedUniqBy(array, iteratee) {
  // When array ==null or length 0, return []
  returnarray ! =null && array.length
    ? // Otherwise call baseSortedUniq(array, iteratee)
      baseSortedUniq(array, iteratee)
    : [];
}

export default sortedUniqBy;
Copy the code