前言
在開(kāi)發(fā)中，我們經(jīng)常會(huì)遇到在數(shù)組中查找指定元素的需求，可能大家覺(jué)得這個(gè)需求過(guò)于簡(jiǎn)單，然而如何優(yōu)雅的去實(shí)現(xiàn)一個(gè) findIndex 和 findLastIndex、indexOf 和 lastIndexOf 方法卻是很少人去思考的。本文就帶著大家一起參考著 underscore 去實(shí)現(xiàn)這些方法。
在實(shí)現(xiàn)前，先看看 ES6 的 findIndex 方法，讓大家了解 findIndex 的使用方法。
findIndex
ES6 對(duì)數(shù)組新增了 findIndex 方法，它會(huì)返回?cái)?shù)組中滿足提供的函數(shù)的第一個(gè)元素的索引，否則返回 -1。
舉個(gè)例子：
function isBigEnough(element) {
return element >= 15;
}
[12, 5, 8, 130, 44].findIndex(isBigEnough); // 3
findIndex 會(huì)找出第一個(gè)大于 15 的元素的下標(biāo)，所以最后返回 3。
是不是很簡(jiǎn)單，其實(shí)，我們自己去實(shí)現(xiàn)一個(gè) findIndex 也很簡(jiǎn)單。
實(shí)現(xiàn)findIndex
思路自然很明了，遍歷一遍，返回符合要求的值的下標(biāo)即可。
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 還有一個(gè)對(duì)應(yīng)的 lastIndexOf 方法，我們也想寫一個(gè)倒序查找的 findLastIndex 函數(shù)。實(shí)現(xiàn)自然也很簡(jiǎn)單，只要修改下循環(huán)即可。
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
然而問(wèn)題在于，findIndex 和 findLastIndex 其實(shí)有很多重復(fù)的部分，如何精簡(jiǎn)冗余的內(nèi)容呢？這便是我們要學(xué)習(xí)的地方，日后面試問(wèn)到此類問(wèn)題，也是加分的選項(xiàng)。
underscore 的思路就是利用傳參的不同，返回不同的函數(shù)。這個(gè)自然是簡(jiǎn)單，但是如何根據(jù)參數(shù)的不同，在同一個(gè)循環(huán)中，實(shí)現(xiàn)正序和倒序遍歷呢？
讓我們直接模仿 underscore 的實(shí)現(xiàn)：
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 的需求算是結(jié)束了，但是又來(lái)了一個(gè)新需求：在一個(gè)排好序的數(shù)組中找到 value 對(duì)應(yīng)的位置，保證插入數(shù)組后，依然保持有序的狀態(tài)。
假設(shè)該函數(shù)命名為 sortedIndex，效果為：
sortedIndex([10, 20, 30], 25); // 2
也就是說(shuō)如果，注意是如果，25 按照此下標(biāo)插入數(shù)組后，數(shù)組變成 [10, 20, 25, 30]，數(shù)組依然是有序的狀態(tài)。
那么這個(gè)又該如何實(shí)現(xiàn)呢？
既然是有序的數(shù)組，那我們就不需要遍歷，大可以使用二分查找法，確定值的位置。讓我們嘗試著去寫一版：
// 第一版
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
現(xiàn)在的方法雖然能用，但通用性不夠，比如我們希望能處理這樣的情況：
// stooges 配角 比如 三個(gè)臭皮匠 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
所以我們還需要再加上一個(gè)參數(shù) iteratee 函數(shù)對(duì)數(shù)組的每一個(gè)元素進(jìn)行處理，一般這個(gè)時(shí)候，還會(huì)涉及到 this 指向的問(wèn)題，所以我們?cè)賯饕粋€(gè) context 來(lái)讓我們可以指定 this，那么這樣一個(gè)函數(shù)又該如何寫呢？
// 第二版
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 也完成了，現(xiàn)在我們嘗試著去寫一個(gè) indexOf 和 lastIndexOf 函數(shù)，學(xué)習(xí) 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
但是即使是數(shù)組的 indexOf 方法也可以多傳遞一個(gè)參數(shù) fromIndex，從 MDN 中看到 fromIndex 的講究可有點(diǎn)多：
設(shè)定開(kāi)始查找的位置。如果該索引值大于或等于數(shù)組長(zhǎng)度，意味著不會(huì)在數(shù)組里查找，返回 -1。如果參數(shù)中提供的索引值是一個(gè)負(fù)值，則將其作為數(shù)組末尾的一個(gè)抵消，即 -1 表示從最后一個(gè)元素開(kāi)始查找，-2 表示從倒數(shù)第二個(gè)元素開(kāi)始查找 ，以此類推。 注意：如果參數(shù)中提供的索引值是一個(gè)負(fù)值，仍然從前向后查詢數(shù)組。如果抵消后的索引值仍小于 0，則整個(gè)數(shù)組都將會(huì)被查詢。其默認(rèn)值為 0。
再看看 lastIndexOf 的 fromIndex：
從此位置開(kāi)始逆向查找。默認(rèn)為數(shù)組的長(zhǎng)度減 1，即整個(gè)數(shù)組都被查找。如果該值大于或等于數(shù)組的長(zhǎng)度，則整個(gè)數(shù)組會(huì)被查找。如果為負(fù)值，將其視為從數(shù)組末尾向前的偏移。即使該值為負(fù)，數(shù)組仍然會(huì)被從后向前查找。如果該值為負(fù)時(shí)，其絕對(duì)值大于數(shù)組長(zhǎng)度，則方法返回 -1，即數(shù)組不會(huì)被查找。
按照這么多的規(guī)則，我們嘗試著去寫第二版：
// 第二版
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);
優(yōu)化
到此為止，已經(jīng)很接近原生的 indexOf 函數(shù)了，但是 underscore 在此基礎(chǔ)上還做了兩點(diǎn)優(yōu)化。
第一個(gè)優(yōu)化是支持查找 NaN。
因?yàn)?NaN 不全等于 NaN，所以原生的 indexOf 并不能找出 NaN 的下標(biāo)。
[1, NaN].indexOf(NaN) // -1
那么我們?cè)撊绾螌?shí)現(xiàn)這個(gè)功能呢？
就是從數(shù)組中找到符合條件的值的下標(biāo)嘛，不就是我們最一開(kāi)始寫的 findIndex 嗎？
我們來(lái)寫一下：
// 第三版
function createIndexOfFinder(dir, predicate) {
return function(array, item, idx){
if () { ... }
// 判斷元素是否是 NaN
if (item !== item) {
// 在截取好的數(shù)組中查找第一個(gè)滿足isNaN函數(shù)的元素的下標(biāo)
idx = predicate(array.slice(i, length), isNaN)
return idx >= 0 ? idx + i: -1;
}
for () { ... }
}
}
var indexOf = createIndexOfFinder(1, findIndex);
var lastIndexOf = createIndexOfFinder(-1, findLastIndex);
第二個(gè)優(yōu)化是支持對(duì)有序的數(shù)組進(jìn)行更快的二分查找。
如果 indexOf 第三個(gè)參數(shù)不傳開(kāi)始搜索的下標(biāo)值，而是一個(gè)布爾值 true，就認(rèn)為數(shù)組是一個(gè)排好序的數(shù)組，這時(shí)候，就會(huì)采用更快的二分法進(jìn)行查找，這個(gè)時(shí)候，可以利用我們寫的 sortedIndex 函數(shù)。
在這里直接給最終的源碼：
// 第四版
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);
// 如果該插入的位置的值正好等于元素的值，說(shuō)明是第一個(gè)符合要求的值
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 的實(shí)現(xiàn)中，只有 indexOf 是支持有序數(shù)組使用二分查找，lastIndexOf 并不支持。
作者：冴羽
github：https://github.com/mqyqingfeng/Blog
掘金主頁(yè)：https://juejin.im/user/58e4b9b261ff4b006b3227f4
segmentfault主頁(yè)：https://segmentfault.com/u/yayu/articles
Vicky丶Amor 經(jīng)授權(quán)轉(zhuǎn)載，版權(quán)歸原作者所有。
