前言

今天是 lodash 的第 9 篇，今天是周五啦，今天带来的是 sortedIndex, sortedIndexBy, sortedIndexOf, sortedLastIndex

看似很多，其实用的也就是一个底层基础方法 - baseSortedIndex

Api

_.sortedIndex([30, 50], 40)

Uses a binary search to determine the lowest index at which value should be inserted into array in order to maintain its sort order.

使用二分法确定 value 在被插入 有序数组 的最小下标

Arguments

1. array  (Array) : The sorted array to inspect.
2. value  ()* : The value to evaluate.

Returns

(number) : Returns the index at which value should be inserted into array.

Example

_.sortedIndex([30, 50], 40);
// => 1

source

function sortedIndex(array, value) {
  return baseSortedIndex(array, value);
}

使用 baseSortedIndex 确定位置

baseSortedIndex

只有数组是 有序 的，才可以使用 二分法

function baseSortedIndex(array,value){
  var low = 0,
      high = array == null ? low : array.length;

      if (typeof value == 'number') {
        while (low < high) {
          var mid = (low + high) >>> 1,
              computed = array[mid];
    
          if (computed < value) {
            low = mid + 1;
          } else {
            high = mid;
          }
        }

        return high;
      }
}

使用 二分法 高效的确定位置，因为 low < high，所以可以使用 high = mid,取不到 mid

可能 对于 >>> 有些陌生

>>> 是 位运算 的一种，名字叫 「无符号右移」, 简单来说，就是 二进制往右移动几位

比如 5 >>> 1 就是 数字 5 转化为 二进制，然后向右移动 1 位，相当于 / 2

0101 向右移动一位 010 , 转为 10 进制是 2

console.log( (2 + 3) >>> 1) // 2
console.log( (3 + 3) >>> 1) // 3

_.sortedIndexBy(array, value, [iteratee=_.identity])

This method is like _.sortedIndex except that it accepts iteratee which is invoked for value and each element of array to compute their sort ranking. The iteratee is invoked with one argument:  (value) .

Arguments

1. array  (Array) : The sorted array to inspect.
2. value  ()* : The value to evaluate.
3. [iteratee=_.identity]  (Function) : The iteratee invoked per element.

Returns

(number) : Returns the index at which value should be inserted into array.

Example

var objects = [{ 'x': 4 }, { 'x': 5 }];
 
_.sortedIndexBy(objects, { 'x': 4 }, function(o) { return o.x; });
// => 0
 
// The `_.property` iteratee shorthand.
_.sortedIndexBy(objects, { 'x': 4 }, 'x');
// => 0

通过最后的 条件， 找到应该被插入的位置

source

function sortedIndexBy(array, value, iteratee) {
  return baseSortedIndexBy(array, value, baseIteratee(iteratee));
}

baseIteratee 简易版

function baseIteratee(iteratee){
    if(typeof iteratee == "function"){
        return iteratee
    }
    
    if(typeof iteratee == "string"){
        return (object)=>{
            return object[iteratee]
        }
    }
}

baseSortedIndexBy

依然用的是 二分法,只不过加上了 iteratee 方法处理数据

function baseSortedIndexBy(array, value, iteratee){
  var low = 0,
      high = array == null ? 0 : array.length;
       
      // 对传入的 value 做处理
      value = iteratee(value);

      while (low < high) {
        let mid = (low + high) >>>1;
        // 对 array[mid] 做同样的处理
        let computed = iteratee(array[mid]);

        if( computed < value){
          low = mid + 1
        }else {
          high = mid
        }
      }
      return high
}

以下图为例

var objects = [{ 'x': 4 }, { 'x': 5 }];
 
_.sortedIndexBy(objects, { 'x': 4 }, function(o) { return o.x; });

// value 执行 获得 4
// array[mid] 执行 获得 4,5
//  相互比较

使用 iteratee 把 x 的值 提取出来，也要把 iteratee(array[mid]) 提取出来，然后做比较

sortedIndexOf(array, value)

This method is like _.indexOf except that it performs a binary search on a sorted array.

Arguments

1. array  (Array) : The array to inspect.
2. value  ()* : The value to search for.

Returns

(number) : Returns the index of the matched value, else -1.

_.sortedIndexOf([4, 5, 5, 5, 6], 5);
// => 1
_.sortedIndexOf([4, 5, 5, 5, 6], 3);
// => -1

这个 和上文的 sortedIndex 有些相似，但是 sortedIndex 是找到合适的插入位置, sortedIndexOf 是在 「已排序」的数组中找到 下标(indexOf)

function sortedIndexOf(array, value) {
    var index = baseSortedIndex(array, value);
    
     if (index < arr.length && array[index] == value) {
          return index;
     }
     
     return -1;
}

原理就是通过 baseSortedIndex 找到 下标，然后判断找到的下标对应的 值 是否与传入的 value 相等

_.sortedLastIndex(array, value)

_.sortedLastIndex([4, 5, 5, 5, 6], 5);
// => 4

和 sortedIndexOf 的区别在于 sortedLastIndex 是找到最后一个相等的位置

需要对 二分法 做一点处理

source

function sortedLastIndex(array, value) {
  return baseSortedIndex(array, value, true);
}

function baseSortedIndex(array, value, retHighest) {
  var low = 0,
      high = array == null ? low : array.length;

  if (typeof value == 'number') {
    while (low < high) {
    
      var mid = (low + high) >>> 1,
          computed = array[mid];
         // 🚀🚀🚀 区别主要在这个地方
      if ( retHighest ? (computed <= value) : (computed < value) ) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return high;
  }
}

如果 computed 和 value 是相同的，low 继续往前走，直到 computed > value 为止，此时就是最右侧

结尾

今天主要是利用 二分法 对 已排序 的数组进行操作