在数组中查找指定元素

2018-06-18

摘要：学习冴羽的博客在数组中查找指定元素

ES6中的findIndex

ES6的findIndex方法会返回数组中满足提供的函数的第一个元素的索引，否则返回 -1

var arr = [0, 1, 2, 3, 4, 5, 6];
function search(value) {
    return value > 3;
}
arr.findIndex(search) // 4

实现findIndex与findLastIndex

正序查找findIndex

// 目标数组，条件函数，this指向
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;
}
findIndex(arr, function (value, i, array) {
    if (value > 3) {
        return true;
    }
})
// 4

倒序查找findLastIndex

function findLastIndex(array, predicate, context) {
    for (var i = array.length - 1; i >= 0; i--) {
        if (predicate.call(context, array[i], i, array)) {
            return i;
        }
    }
    return -1;
}
findLastIndex(arr, function (value, i, array) {
    if (value > 3) {
        return true;
    }
})
// 6

精简createIndexFinder

结合正序和倒序实现一个利用参数的不同，返回不同函数的方法（underscore）

// dir为1时是正序，-1时是倒序
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

在一个排好序的数组中插入值，保证插入后数组仍是有序状态。有序数组可以使用二分法加快速度

function sortedIndex(array, number) {
    var low = 0, high = array.length;
    while (low < high) {
        var mid = Math.floor((low + high) / 2);
        if (array[mid] < number){
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return high;
}

如果数组元素是个对象，想要按照某个属性值来排序怎么办？需要一个方法将数组的每一个元素都进行处理并返回关键属性值（注意 this 的指向），然后按照上面的方法进行排序

function cb(fn, context) {
    // 非严格模式下，函数作用域中的undefined（NaN，Infinity等）可以被重写，使用 void 0 返回 undefined 避免因 undefined 被重写而造成的错误（还可以减少3个字节）
    // void后面跟任何值都是返回undefined
    if (context === void 0) {
        return fn;
    }
    return function () {
        return fn.apply(context, arguments);
    };
}

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;
}

var class1 = [{ name: "xiaoming", number: 123 }, { name: "xiaohong", number: 200 }];
var newStudent = { name: "dawang", number: 145 };
sortedIndex(class1, newStudent, function (student) {
    return student.number;
}) // 1

实现 indexOf 与 lastIndexOf

参照 findIndex 和 FindLastIndex 的方式，写一个可以生成 indexOf 和 lastIndexOf 的方法

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); // 1

但是 indexOf 还可以传递第二个参数 fromIndex，用于控制查找范围

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

lastIndexOf的fromIndex

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

function createIndexOfFinder(dir) {
    return function (array, item, fromIndex) {
        var length = array.length;
        var index = 0;
        if (typeof fromIndex === "number") {
            // 确定起始索引思想：排除不合理的范围。正向查找时要保证起始索引为非负数；逆向查询时要保证起始索引不能超出目标数组
            if (fromIndex > 0) {
                // 正向起始索引
                index = fromIndex >= 0 ? fromIndex : Math.max(length + fromIndex, 0);
            } else {
                // 逆向起始索引+1，即目标数组符合条件的长度
                length = fromIndex >= 0 ? Math.min(fromIndex + 1, length) : index + length + 1;
            }
        }

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

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

优化

underscore在此基础上还做了两点优化：
1.支持查找 NaN
利用 NaN !== NaN 的特性来判断要查询的元素是不是 NaN，如果是就用上面的 findIndex/findLastIndex 查找并返回该元素的索引

function createIndexOfFinder(dir, predicate) {
    return function (array, item, fromIndex) {
        var length = array.length;
        var index = 0;
        if () {
            ...
        }

        // 判断是不是 NaN
        if(item !== item) {
            fromIndex = predicate(array.slice(i,length), isNaN);
            return fromIndex >= 0 ? fromIndex + i : -1;
        }

        for () {
            ...
        }
        return -1;
    }
}

2.支持对有序数组进行更快的二分查找
当对有序数组进行正想查找时，返回的函数（indexOf）的第三个参数不是数值而是布尔 true，就认为数组是一个排好序的数组，调用 sortedIndex 采用用二分法进行更快的查询

function createIndexOfFinder(dir, predicate, sortedIndex) {
    return function (array, item, fromIndex) {
        var length = array.length;
        var index = 0;
        if (typeof fromIndex === "number") {
            // 确定起始索引思想：排除不合理的范围。正向查找时要保证起始索引为非负数；逆向查询时要保证起始索引不能超出目标数组
            if (fromIndex > 0) {
                // 正向起始索引
                index = fromIndex >= 0 ? fromIndex : Math.max(length + fromIndex, 0);
            } else {
                // 逆向起始索引+1，即目标数组符合条件的长度
                length = fromIndex >= 0 ? Math.min(fromIndex + 1, length) : index + length + 1;
            }
        } else if(fromIndex && sortedIndex && length){
            // 二分法查找数组中第一个不比目标元素小的数组元素，如果这个数组元素与目标元素相等则返回该数组元素的索引；否则就是数组中没有与目标元素相等的元素，返回-1
            fromIndex = sortedIndex(array, item);
            return array[fromIndex] === item ? fromIndex : -1;
        }

        // 判断是不是 NaN
        if(item !== item) {
            fromIndex = predicate(array.slice(index, length), isNaN);
            return fromIndex >= 0 ? fromIndex + index : -1;
        }

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

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