js专题——数组中查找指定元素（转）

前⾔

在开发中，我们经常会遇到在数组中查找指定元素的需求，可能⼤家觉得这个需求过于简单，然⽽如何优雅的去实现⼀个 findIndex 和findLastIndex、indexOf 和 lastIndexOf ⽅法却是很少⼈去思考的。本⽂就带着⼤家⼀起参考着 underscore 去实现这些⽅法。在实现前，先看看 ES6 的 findIndex ⽅法，让⼤家了解 findIndex 的使⽤⽅法。

findIndex

ES6 对数组新增了 findIndex ⽅法，它会返回数组中满⾜提供的函数的第⼀个元素的索引，否则返回 -1。举个例⼦：

function isBigEnough(element) { return element >= 15;}

[12, 5, 8, 130, 44].findIndex(isBigEnough); // 3

findIndex 会找出第⼀个⼤于 15 的元素的下标，所以最后返回 3。是不是很简单，其实，我们⾃⼰去实现⼀个 findIndex 也很简单。

实现findIndex

思路⾃然很明了，遍历⼀遍，返回符合要求的值的下标即可。

function findIndex(array, predicate, context) { for (var i = 0; i < array.length; i++) {

if (predicate.call(context, array[i], i, array)) return i; }

return -1;}

console.log(findIndex([1, 2, 3, 4], function(item, i, array){ if (item == 3) return true;})) // 2

findLastIndex

findIndex 是正序查找，但正如 indexOf 还有⼀个对应的 lastIndexOf ⽅法，我们也想写⼀个倒序查找的 findLastIndex 函数。实现⾃然也很简单，只要修改下循环即可。

function findLastIndex(array, predicate, context) { var length = array.length;

for (var i = length; i >= 0; i--) {

if (predicate.call(context, array[i], i, array)) return i; }

return -1;}

console.log(findLastIndex([1, 2, 3, 4], function(item, index, array){ if (item == 1) return true;})) // 0

createIndexFinder

然⽽问题在于，findIndex 和 findLastIndex 其实有很多重复的部分，如何精简冗余的内容呢？这便是我们要学习的地⽅，⽇后⾯试问到此类问题，也是加分的选项。

underscore 的思路就是利⽤传参的不同，返回不同的函数。这个⾃然是简单，但是如何根据参数的不同，在同⼀个循环中，实现正序和倒序遍历呢？

让我们直接模仿 underscore 的实现：

function createIndexFinder(dir) {

return function(array, predicate, context) { var length = array.length;

var index = dir > 0 ? 0 : length - 1;

for (; index >= 0 && index < length; index += dir) {

if (predicate.call(context, array[index], index, array)) return index; } return -1; }}

var findIndex = createIndexFinder(1);

var findLastIndex = createIndexFinder(-1);

sortedIndex

findIndex 和 findLastIndex 的需求算是结束了，但是⼜来了⼀个新需求：在⼀个排好序的数组中找到 value 对应的位置，保证插⼊数组后，依然保持有序的状态。

假设该函数命名为 sortedIndex，效果为：

sortedIndex([10, 20, 30], 25); // 2

也就是说如果，注意是如果，25 按照此下标插⼊数组后，数组变成 [10, 20, 25, 30]，数组依然是有序的状态。那么这个⼜该如何实现呢？

既然是有序的数组，那我们就不需要遍历，⼤可以使⽤⼆分查找法，确定值的位置。让我们尝试着去写⼀版：

// 第⼀版

function sortedIndex(array, obj) { var low = 0, high = array.length; while (low < high) {

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

return high;};

console.log(sortedIndex([10, 20, 30, 40, 50], 35)) // 3

现在的⽅法虽然能⽤，但通⽤性不够，⽐如我们希望能处理这样的情况：

// stooges 配⾓ ⽐如 三个臭⽪匠 The Three Stooges

var stooges = [{name: 'stooge1', age: 10}, {name: 'stooge2', age: 30}];var result = sortedIndex(stooges, {name: 'stooge3', age: 20}, function(stooge){ return stooge.age});

console.log(result) // 1

所以我们还需要再加上⼀个参数 iteratee 函数对数组的每⼀个元素进⾏处理，⼀般这个时候，还会涉及到 this 指向的问题，所以我们再传⼀个 context 来让我们可以指定 this，那么这样⼀个函数⼜该如何写呢？

// 第⼆版

function cb(fn, context) { return function(obj) {

return fn ? fn.call(context, obj) : obj; }}

function sortedIndex(array, obj, iteratee, context) { iteratee = cb(iteratee, context)

var low = 0, high = array.length; while (low < high) {

var mid = Math.floor((low + high) / 2);

if (iteratee(array[mid]) < iteratee(obj)) low = mid + 1; else high = mid; }

return high;};

indexOf

sortedIndex 也完成了，现在我们尝试着去写⼀个 indexOf 和 lastIndexOf 函数，学习 findIndex 和 FindLastIndex 的⽅式，我们写⼀版：

// 第⼀版

function createIndexOfFinder(dir) { return function(array, item){ var length = array.length;

var index = dir > 0 ? 0 : length - 1;

for (; index >= 0 && index < length; index += dir) { if (array[index] === item) return index; }

return -1; }}

var indexOf = createIndexOfFinder(1);var lastIndexOf = createIndexOfFinder(-1);var result = indexOf([1, 2, 3, 4, 5], 2);console.log(result) // 1

fromIndex

但是即使是数组的 indexOf ⽅法也可以多传递⼀个参数 fromIndex，从 MDN 中看到 fromIndex 的讲究可有点多：

设定开始查找的位置。如果该索引值⼤于或等于数组长度，意味着不会在数组⾥查找，返回 -1。如果参数中提供的索引值是⼀个负值，则将其作为数组末尾的⼀个抵消，即 -1 表⽰从最后⼀个元素开始查找，-2 表⽰从倒数第⼆个元素开始查找 ，以此类推。注意：如果参数中提供的索引值是⼀个负值，仍然从前向后查询数组。如果抵消后的索引值仍⼩于 0，则整个数组都将会被查询。其默认值为 0。再看看 lastIndexOf 的 fromIndex：

从此位置开始逆向查找。默认为数组的长度减 1，即整个数组都被查找。如果该值⼤于或等于数组的长度，则整个数组会被查找。如果为负值，将其视为从数组末尾向前的偏移。即使该值为负，数组仍然会被从后向前查找。如果该值为负时，其绝对值⼤于数组长度，则⽅法返回 -1，即数组不会被查找。按照这么多的规则，我们尝试着去写第⼆版：

// 第⼆版

function createIndexOfFinder(dir) { return function(array, item, idx){ var length = array.length; var i = 0;

if (typeof idx == \"number\") { if (dir > 0) {

i = idx >= 0 ? idx : Math.max(length + idx, 0); }

else {

length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1; } }

for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) { if (array[idx] === item) return idx; }

return -1; }}

var indexOf = createIndexOfFinder(1);var lastIndexOf = createIndexOfFinder(-1);

优化

到此为⽌，已经很接近原⽣的 indexOf 函数了，但是 underscore 在此基础上还做了两点优化。第⼀个优化是⽀持查找 NaN。

因为 NaN 不全等于 NaN，所以原⽣的 indexOf 并不能找出 NaN 的下标。

[1, NaN].indexOf(NaN) // -1

那么我们该如何实现这个功能呢？

就是从数组中找到符合条件的值的下标嘛，不就是我们最⼀开始写的 findIndex 吗？我们来写⼀下：

// 第三版

function createIndexOfFinder(dir, predicate) { return function(array, item, idx){ if () { ... }

// 判断元素是否是 NaN if (item !== item) {

// 在截取好的数组中查找第⼀个满⾜isNaN函数的元素的下标 idx = predicate(array.slice(i, length), isNaN) return idx >= 0 ? idx + i: -1; }

for () { ... } }}

var indexOf = createIndexOfFinder(1, findIndex);

var lastIndexOf = createIndexOfFinder(-1, findLastIndex);

第⼆个优化是⽀持对有序的数组进⾏更快的⼆分查找。

如果 indexOf 第三个参数不传开始搜索的下标值，⽽是⼀个布尔值 true，就认为数组是⼀个排好序的数组，这时候，就会采⽤更快的⼆分法进⾏查找，这个时候，可以利⽤我们写的 sortedIndex 函数。在这⾥直接给最终的源码：

// 第四版

function createIndexOfFinder(dir, predicate, sortedIndex) { return function(array, item, idx){ var length = array.length; var i = 0;

if (typeof idx == \"number\") { if (dir > 0) {

i = idx >= 0 ? idx : Math.max(length + idx, 0); }

else {

length = idx >= 0 ? Math.min(idx + 1, length) : idx + length + 1; } }

else if (sortedIndex && idx && length) { idx = sortedIndex(array, item);

// 如果该插⼊的位置的值正好等于元素的值，说明是第⼀个符合要求的值 return array[idx] === item ? idx : -1; }

// 判断是否是 NaN if (item !== item) {

idx = predicate(array.slice(i, length), isNaN) return idx >= 0 ? idx + i: -1; }

for (idx = dir > 0 ? i : length - 1; idx >= 0 && idx < length; idx += dir) { if (array[idx] === item) return idx; }

return -1; }}

var indexOf = createIndexOfFinder(1, findIndex, sortedIndex);var lastIndexOf = createIndexOfFinder(-1, findLastIndex);

值得注意的是：在 underscore 的实现中，只有 indexOf 是⽀持有序数组使⽤⼆分查找，lastIndexOf 并不⽀持。 （转）