如何优雅地写一个「在数组中寻找指定元素」的方法

[lessfish]

Why underscore

（觉得这部分眼熟的可以直接跳到下一段了...）

最近开始看 underscore.js 源码，并将 underscore.js 源码解读 放在了我的 2016 计划中。

阅读一些著名框架类库的源码，就好像和一个个大师对话，你会学到很多。为什么是 underscore？最主要的原因是 underscore 简短精悍（约 1.5k 行），封装了 100 多个有用的方法，耦合度低，非常适合逐个方法阅读，适合楼主这样的 JavaScript 初学者。从中，你不仅可以学到用 void 0 代替 undefined 避免 undefined 被重写等一些小技巧 ，也可以学到变量类型判断、函数节流&函数去抖等常用的方法，还可以学到很多浏览器兼容的 hack，更可以学到作者的整体设计思路以及 API 设计的原理（向后兼容）。

之后楼主会写一系列的文章跟大家分享在源码阅读中学习到的知识。

• underscore-1.8.3 源码解读项目地址 https://github.com/hanzichi/underscore-analysis
• underscore-1.8.3 源码全文注释 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/underscore-1.8.3-analysis.js
• underscore-1.8.3 源码解读系列文章 https://github.com/hanzichi/underscore-analysis/issues

欢迎围观~ （如果有兴趣，欢迎 star & watch~）您的关注是楼主继续写作的动力

题外话

先说点题外话。

自从 5 月 16 日开始 underscore 系列解读文章，目前已经收获了 160+ star，在这里子迟也感谢大家的支持，并将继续努力分享源码里的干货。有朋友私信我说好几天没看到更新，在此也请大家原谅，毕竟我把它当成了今年的计划之一，而且平时也要上班工作，只能利用闲暇时间，而且楼主本人对文章的质量要求比较高，如果是一律的流水文章，读者学不到什么东西，自己的那关都过不了。其实如果有心，应该能发现 underscore-1.8.3 源码全文注释 一直有在更新（注释行数已经快破 1000 了）。

Main

言归正传，上一章 中我们结束了 Object 扩展方法部分，今天开始来解读 Array 部分的扩展方法。其实 JavaScript 中的数组是我最喜欢的类型，能模拟栈、队列等数据结构，还能随意插入元素（splice），非常的灵活，这点做过 leetcode 的应该都深有体会（这里也顺便安利下我的 leetcode 题解 Repo https://github.com/hanzichi/leetcode）。

今天要讲的是，如何在数组中寻找元素，对应 underscore 中的 _.findIndex，_.findLastIndex，_.indexOf，_.lastIndexOf 以及 _.sortIndex 方法。

等等，是不是有点眼熟，没错，JavaScript 中已经部署了 indexOf 方法（ES5）以及 findIndex 方法（ES6），这点不介绍了，大家可以自行学习。

我们先来看 _.findIndex 和 _.findLastIndex 函数。如果了解过 Array.prototype.findIndex() 方法，会非常容易。_.findIndex 的作用就是从一个数组中找到第一个满足某个条件的元素，_.findLastIndex 则是找到最后一个（或者说倒序查找）。

举个简单的例子：

var arr = [1, 3, 5, 2, 4, 6];

var isEven = function(num) {
  return !(num & 1);
};

var idx = _.findIndex(arr, isEven);
// => 3

直接看源码，注释已经写的非常清楚了。这里要注意这个 predicate 函数，其实就是把数组中的元素传入这个参数，返回一个布尔值。如果返回 true，则表示满足这个条件，如果 false 则相反。

// Generator function to create the findIndex and findLastIndex functions
// dir === 1 => 从前往后找 
// dir === -1 => 从后往前找
function createPredicateIndexFinder(dir) {
  // 经典闭包
  return function(array, predicate, context) {
    predicate = cb(predicate, context);

    var length = getLength(array);

    // 根据 dir 变量来确定数组遍历的起始位置
    var index = dir > 0 ? 0 : length - 1;

    for (; index >= 0 && index < length; index += dir) {
      // 找到第一个符合条件的元素
      // 并返回下标值
      if (predicate(array[index], index, array)) return index;
    }

    return -1;
  };
}

// Returns the first index on an array-like that passes a predicate test
// 从前往后找到数组中 `第一个满足条件` 的元素，并返回下标值
// 没找到返回 -1
// _.findIndex(array, predicate, [context]) 
_.findIndex = createPredicateIndexFinder(1);

// 从后往前找到数组中 `第一个满足条件` 的元素，并返回下标值
// 没找到返回 -1
// _.findLastIndex(array, predicate, [context]) 
_.findLastIndex = createPredicateIndexFinder(-1);

接下来看 _.sortIndex 方法，这个方法无论使用还是实现都非常的简单。如果往一个有序数组中插入元素，使得数组继续保持有序，那么这个插入位置是？这就是这个方法的作用，有序，很显然用二分查找即可。不多说，直接上源码。

// _.sortedIndex(list, value, [iteratee], [context]) 
_.sortedIndex = function(array, obj, iteratee, context) {
  // 注意 cb 方法
  // iteratee 为空 || 为 String 类型（key 值）时会返回不同方法
  iteratee = cb(iteratee, context, 1);

  // 经过迭代函数计算的值
  var value = iteratee(obj);

  var low = 0, high = getLength(array);

  while (low < high) {
    var mid = Math.floor((low + high) / 2);
    if (iteratee(array[mid]) < value) low = mid + 1; else high = mid;
  }

  return low;
};

最后我们说说 _.indexOf 和 _.lastIndexOf 方法。

ES5 引入了 indexOf 和 lastIndexOf 方法，但是 IE < 9 不支持，面试时让你写个 Polyfill，你会怎么做（可以把 underscore 的实现看做 Polyfill）？如何能让面试官满意？首先如果分开来写，即两个方法相对独立地写，很显然代码量会比较多，因为两个方法功能相似，所以可以想办法调用一个方法，将不同的部分当做参数传入，减少代码量。其次，如果数组已经有序，是否可以用更快速的二分查找算法？这点会是加分项。

源码实现：

  // Generator function to create the indexOf and lastIndexOf functions
  // _.indexOf = createIndexFinder(1, _.findIndex, _.sortedIndex);
  // _.lastIndexOf = createIndexFinder(-1, _.findLastIndex);
  function createIndexFinder(dir, predicateFind, sortedIndex) {

    // API 调用形式
    // _.indexOf(array, value, [isSorted]) 
    // _.indexOf(array, value, [fromIndex]) 
    // _.lastIndexOf(array, value, [fromIndex]) 
    return function(array, item, idx) {
      var i = 0, length = getLength(array);

      // 如果 idx 为 Number 类型
      // 则规定查找位置的起始点
      // 那么第三个参数不是 [isSorted]
      // 所以不能用二分查找优化了
      // 只能遍历查找
      if (typeof idx == 'number') {
        if (dir > 0) { // 正向查找
          // 重置查找的起始位置
          i = idx >= 0 ? idx : Math.max(idx + length, i);
        } else { // 反向查找
          // 如果是反向查找，重置 length 属性值
          length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1;
        }
      } else if (sortedIndex && idx && length) {
        // 能用二分查找加速的条件
        // 有序 & idx !== 0 && length !== 0

        // 用 _.sortIndex 找到有序数组中 item 正好插入的位置
        idx = sortedIndex(array, item);

        // 如果正好插入的位置的值和 item 刚好相等
        // 说明该位置就是 item 第一次出现的位置
        // 返回下标
        // 否则即是没找到，返回 -1
        return array[idx] === item ? idx : -1;
      }

      // 特判，如果要查找的元素是 NaN 类型
      // 如果 item !== item
      // 那么 item => NaN
      if (item !== item) {
        idx = predicateFind(slice.call(array, i, length), _.isNaN);
        return idx >= 0 ? idx + i : -1;
      }

      // O(n) 遍历数组
      // 寻找和 item 相同的元素
      // 特判排除了 item 为 NaN 的情况
      // 可以放心地用 `===` 来判断是否相等了
      for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) {
        if (array[idx] === item) return idx;
      }

      return -1;
    };
  }

  // Return the position of the first occurrence of an item in an array,
  // or -1 if the item is not included in the array.
  // If the array is large and already in sort order, pass `true`
  // for **isSorted** to use binary search.
  // _.indexOf(array, value, [isSorted]) 
  // 找到数组 array 中 value 第一次出现的位置
  // 并返回其下标值
  // 如果数组有序，则第三个参数可以传入 true
  // 这样算法效率会更高（二分查找）
  // [isSorted] 参数表示数组是否有序
  // 同时第三个参数也可以表示 [fromIndex] （见下面的 _.lastIndexOf）
  _.indexOf = createIndexFinder(1, _.findIndex, _.sortedIndex);

  // 和 _indexOf 相似
  // 反序查找
  // _.lastIndexOf(array, value, [fromIndex]) 
  // [fromIndex] 参数表示从倒数第几个开始往前找
  _.lastIndexOf = createIndexFinder(-1, _.findLastIndex);

这里有一点要注意，_.indexOf 方法的第三个参数可以表示 [fromIndex] 或者 [isSorted]，而 _.lastIndexOf 的第三个参数只能表示 [fromIndex]，我们从代码中便可以轻易看出：

_.indexOf = createIndexFinder(1, _.findIndex, _.sortedIndex);
_.lastIndexOf = createIndexFinder(-1, _.findLastIndex);

关于这点我也百思不得其解，不知道做这个限制是为了什么考虑，欢迎探讨~

最后给出本文涉及的五个方法的源码位置 https://github.com/hanzichi/underscore-analysis/blob/master/underscore-1.8.3.js/src/underscore-1.8.3.js#L613-L673

[daijinma]

var isEven = function(num) {
  return !(num & 1);
};

这里面的 & 怎么理解？

[lessfish]

@daijinma
& 位运算与，num & 1 相当于 num % 2
关于位运算，如果有兴趣可以看下我以前写的位运算系列文章 http://www.cnblogs.com/zichi/category/732474.html

[shaunzeng]

hey, awesome article! really enjoyed learning from it!

I have a question, how is '.findIndex' not checking if it's an array or not? and how come '.sortedIndex' is not checking the obj type, but still make it work on objects?

By the way, I speak Chinese so you could response in Chinese. Really appreciate!

Thanks

[lessfish]

@shaunzeng
For the first question, Underscore does not do any static type checking, I think it's better to throw an error when passing a para to '.findIndex' which is not an array.

For the second, maybe '.findIndex' and '.sortedIndex' are both working on arrays? not on objects for they're both Array Functions?

[aleen42]

是不是因为它的二分查找并没有针对倒序的有序数组处理，因此不给予 isSorted 选项

[WangNianyi2001]

@shaunzeng Since you speak Chinese, why did you comment in English in the first time?

[Ocean5app]

cb(predicate, context) 中的cb方法是如何定义的？哪里能找到