查找数组指定元素
ES6 findIndex
findIndex它会返回数组中满足提供的函数的第一个元素的索引，否则返回 -1
let arr = [1,15,15,45,24,37,298,111,15]
arr.findIndex(isBigEnough)
isBigEnough(element){
return element > 200
},
模拟实现findIndex
findIndex(arr,func,context){
for(let i =0;i<arr.length;i++){
if (func.call(context, arr[i])) return i;
}
return -1
},
模拟实现findLastIndex
跟findIndex差不多，只不过是倒序查找
findLastIndex(arr,func,context){
var length = arr.length
for(let i = length-1 ;i>=0;i--){
if(func.call(context,arr[i])) return i
}
return -1
},
createIndexFinder
观察可以知道findIndex 和findLastIndex的实现原理基本相同，区别只在于查找顺讯，那么如何通过实现一个函数，通过不同的传参来判断是使用findIndex还是findLastIndex呢？
实现：
createIndexFinder(dir){
return function(arr,func,context){
let length = arr.length;
let index = dir > 0 ? 0 : length -1
for(;index >=0 && index < length; index+=dir){
if(func.call(context,arr[index])) return index
}
return -1
}
},
sortedIndex
新的需求：如何在一个排好序的数组中找到 value 对应的位置，保证插入数组后，依然保持有序的状态？
比如：sortedIndex([10, 20, 30], 25); // 2
如果是有序数组，那我们就不采用遍历的形式，采用二分法
sortedIndex(arr,target){
let low = 0,high = arr.length;
while(low<high){
let mid = Math.floor((high+low)/2)
if(arr[mid]<target){
low = mid + 1
}else{
high = mid
}
}
return high
},
看上去不错，基本实现了我们的要求，但还不够好，如果我想实现下面这种情况要怎么处理？
// 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
进阶实现：
sortedIndex(arr,target,iteratee,context){
iteratee = this.cb(iteratee,context)
let low = 0,high = arr.length;
while(low < high){
let mid = Math.floor((low + high) / 2)
if(iteratee(arr[mid]) < iteratee(target)){
low = mid + 1
}else{
high = mid
}
}
return high
},
// 处理函数this问题
cb(func,context){
if(context === void 0){
return func
}else{
return func.apply(context,arguments)
}
},
indexOf/lastIndexOf
现在尝试手写一个indexOf/lastIndexOf
createIndexOfFinder(dir){
return function(arr,item){
let length = arr.length
let index = dir > 0 ? 0 : length - 1
for(;index>= 0 && index<length;index+=dir){
if(arr[index] === item){
return index
}
}
return -1
}
},
var indexOf = createIndexOfFinder(1);
var lastIndexOf = createIndexOfFinder(-1);
indexOf和lastIndexOf都支持第二个参数fromIndex表示开始查找的位置。
在MDN上对fromIndex的解释如下：
- indexOf:
fromIndex
开始查找的位置。如果该索引值大于或等于数组长度，意味着不会在数组里查找，返回-1。如果参数中提供的索引值是一个负值，则将其作为数组末尾的一个抵消，即-1表示从最后一个元素开始查找，-2表示从倒数第二个元素开始查找 ，以此类推。 注意：如果参数中提供的索引值是一个负值，并不改变其查找顺序，查找顺序仍然是从前向后查询数组。如果抵消后的索引值仍小于0，则整个数组都将会被查询。其默认值为0.
比如：
var array = [2, 5, 9,11,13];
array.indexOf(2, 3); // -1 表示从第三个位置开始向后查找
array.indexOf(5, -4) // 1 -4表示从倒数第四个位置开始向后查找
- lastIndexOf
fromIndex
从此位置开始逆向查找。默认为数组的长度减 1(arr.length - 1)，即整个数组都被查找。如果该值大于或等于数组的长度，则整个数组会被查找。如果为负值，将其视为从数组末尾向前的偏移。即使该值为负，数组仍然会被从后向前查找。如果该值为负时，其绝对值大于数组长度，则方法返回 -1，即数组不会被查找。
var array = [2, 5, 9,2,11,13];
array.lastIndexOf(2,2) // 0 从第二个位置向前查找
array.lastIndexOf(2,-3) // 3 从后向前数三个位置开始向前查找
根据以上规则，我们实现第二版
createIndexOfFinder(dir){
return function(arr,item,idx){
let length = arr.length
let i=0
if(typeof idx == 'number'){
if(dir > 0){
i = idx > 0 ? idx : Math.max(idx,length)
}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(arr[idx] === item){
return idx
}
}
return -1
}
},
优化
主要围绕下面两点进行
- 如何支持查找NaN
- 支持对有序数组更快的二分查找，如果formIndex传一个true就表示数组有序
根据以上要求，看下最终实现方法
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 并不支持
