es6 的 findIndex

es6 对数组新增了 findIndex 方法，返回数组中满足提供的函数的第一个元素的索引，否则返回 -1。

例子

function isBigEnough(element) {
    return element >= 15;
}
[12, 5, 8, 130, 44].findIndex(isBigEnough);  // 3

实现 findIndex

遍历一次，返回符合条件的第一个元素的索引值。

function findIndex(array, predicate, context) {
    for (let i = 0; i < array.length; i++) {
        if (predicate.call(context, array[i], i, array)) return i;
    }
    return -1;
}

实现 findLastIndex

findIndex 是正序，那怎样实现倒序查找了？修改一下循环就可以了。

function findLastIndex(array, predicate, context) {
    let length = array.length;
    for (let i = length - 1; i >= 0; i--) {
        if (predicate.call(context, array[i], i, array)) return i;
    }
    return -1;
}
console.log(findLastIndex([1, 2, 3, 4, 5, 6, 6, 6, 6], function (item, index, array) {
    if (item === 6) return true;
})); // 8

合并 findIndex 和 findLastIndex

上面的两个实现，代码重复太多了，那怎样合并到一起了？很简单利用传参的不同，返回不同的函数。

// 根据传参的不同返回不同的函数
function createIndexFinder(dir) {
    return function (array, predicate, context) {
        let length = array.length;
        let index = dir > 0 ? 0 : length - 1;
        // index >= 0 是倒序的临界条件；index < length 是正序的临界条件
        for (; index >= 0 && index < length; index += dir) {
            if (predicate.call(context, array[index], index, array)) return index;
        }
        return -1;
    };
}
const findIndex = createIndexFinder(1);
const findLastIndex = createIndexFinder(-1);

sortedIndex

现在有个新需求：在一个排好序的数组中找到 value 对应的位置，保证插入到数组后，依然是有序的。

例子（假设有个叫 sortedIndex 的函数）

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

数组变成 [10, 20, 25, 30] 依然是有序的。

可以利用二分法来实现。

function sortedIndex(array, obj) {
    let low = 0, high = array.length;
    while (low < high) {
        let 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

支持更多情况，比如添加一个判断函数。

function cb(func, context) {
    if (context === void 0) return func;
    return function () {
        return func.apply(context, arguments);
    };
}
function sortedIndexTwo(array, obj, iteratee, context) {
    iteratee = cb(iteratee, context);
    let low = 0, high = array.length;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (iteratee(array[mid]) < iteratee(obj)) low = mid + 1;
        else high = mid;
    }
    return high;
}
const stooges = [{name: 'stooge1', age: 10}, {name: 'stooge2', age: 30}];
const  result = sortedIndexTwo(stooges, {name: 'stooge3', age: 20}, function(stooge){
    return stooge.age
});
console.log(result) // 1

实现 indexOf 和 lastIndexOf

也很简单，直接遍历。

function createIndexOfFinder(dir) {
    return function (array, item) {
        let length = array.length;
        let index = dir > 0 ? 0 : length - 1;
        for (; index >= 0 && index < length; index += dir) {
            if (array[index] === item) return index;
        }
        return -1;
    };
}
const indexOf = createIndexOfFinder(1);
const lastIndexOf = createIndexOfFinder(-1);
const result = indexOf([1, 2, 3, 4, 5], 2);
console.log(result); // 1

indexOf 和 lastIndexOf 都支持 fromIndex 参数，来看看 mdn 是怎样解释的。

indexOf

开始查找的位置。如果该索引值大于或等于数组长度，意味着不会在数组里查找，返回-1。如果参数中提供的索引值是一个负值，则将其作为数组末尾的一个抵消，即-1表示从最后一个元素开始查找，-2表示从倒数第二个元素开始查找，以此类推。注意：如果参数中提供的索引值是一个负值，并不改变其查找顺序，查找顺序仍然是从前向后查询数组。如果抵消后的索引值仍小于0，则整个数组都将会被查询。其默认值为0。

fromIndex
从此位置开始逆向查找。默认为数组的长度减 1(arr.length - 1)，即整个数组都被查找。如果该值大于或等于数组的长度，则整个数组会被查找。如果为负值，将其视为从数组末尾向前的偏移。即使该值为负，数组仍然会被从后向前查找。如果该值为负时，其绝对值大于数组长度，则方法返回 -1，即数组不会被查找。

实现一下

function createIndexOfFinder(dir) {
    return function (array, item, idx) {
        let length = array.length;
        let i = 0;
        if (typeof idx == "number") {
            if (dir > 0) {
                // 正序
                i = idx >= 0 ? idx : Math.max(length + idx, 0);
            } else {
                // 倒序
        // 这里的 + 1 是兼容下面 for 循环中第二个 length。
        // 这里的 + 1 在下面的 for 中第一个 length 也减去。
                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;
    };
}

支持查找 NaN

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 () { ... };
    }
}
const indexOf = createIndexOfFinder(1, findIndex);
const lastIndexOf = createIndexOfFinder(-1, findLastIndex);

对有序的数组使用二分查找。

如果 indexOf 的第三个参数不传开始搜索的下标值，而是一个 true，就认为数组是一个排好序的数组。就使用二分查找。我们可以利用 sortedIndex。

注意：倒序不支持。

最终代码

function createIndexOfFinder(dir, predicate, sortedIndex) {
    return function (array, item, idx) {
        let length = array.length;
        let i = 0;
        if (typeof idx == "number") {
            if (dir > 0) {
        // 正序
                i = idx >= 0 ? idx : Math.max(length + idx, 0);
            } else {
        // 倒序
        // 这里的 + 1 是兼容下面 for 循环中第二个 length。
        // 这里的 + 1 在下面的 for 中第一个 length 也减去。
                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;
    };
}
const indexOf = createIndexOfFinder(1, findIndex, sortedIndex);
const lastIndexOf = createIndexOfFinder(-1, findLastIndex);
console.log(indexOf([NaN, 1, 3, 4], NaN));

参考：

[1] JavaScript专题之学underscore在数组中查找指定元素
[2] indexOf
[3] lastIndexOf
[4] findIndex
[5] isNaN

Programing learning note