Look at this crazy question... I have an array with 30.000 items, and I have to run something like this over it:
const bigArray = [
{ createdAt: 1 },
{ createdAt: 2 },
{ createdAt: 3 },
// And so on... 30.000
];
const found = bigArray.find(x => x.createdAt > 29950)
And the thing here, is that I know that 100% of the time, that element will be in the index 29.950 (approx). Because that array is already sorted by createdAt (coming from the backend)
How does .find works? Does it iterates starting from the first element? Is there a way to say "I know it's closer to the end... Change your behavior"?
Of course there is the alternative of doing something like:
bigArray.reverse()
const prevIndex = bigArray.findIndex(x => x.createdAt <= 29950);
const found = bigArray[prevIndex - 1];
bigArray.reverse()
But I'm not sure if that's gonna be actually worst (because of the fact that there we'll also have some multiples unnecessary iterations... I guess).
Who can give me some clues about this? It's not that I have a bug here... Not even a performance issue (because 30.000 is not that much), but, feels like there should be something there, and I never hear about it in ~16 years working on JavaScript
Thanks so much!
Based upon the documentation here, it appears that find is O(n) time complexity, where n is length of the array.
Since your elements are sorted, you can try to do binary search and reduce time complexity to O(log n).
This is the basic binary search iterative algorithm:
function binarySearchIterative (nums, target) {
let res = -1;
let left = 0;
let right = nums.length;
while (left <= right && res === -1) {
const mid = Math.floor(left + (right - left)/2);
if (nums[mid] === target) {
res = mid;
}
else if (nums[mid] > target) {
right--;
}
else {
left++;
}
}
return res;
};
I'm not aware of any options for Array.prototype.findIndex that start from the end... I do know for sure that using Array.prototype.reverse is very expensive and you could make your own algorithm like this if you know that you're likely to find the result you need near the end:
const bigArray = [
{ createdAt: 1 },
{ createdAt: 2 },
{ createdAt: 3 }
];
// Add the function to Array.prototype
Array.prototype.findIndexFromEnd = function (cond) {
for(let i = this.length - 1; i >= 0; i--) {
if(cond(this[i])) return i;
}
return -1;
}
// Gives 1 as expected
console.log(bigArray.findIndexFromEnd(x => x.createdAt == 2));
// Or use an external function if you don't want to edit the prototype
function findIndexFromEnd(array, cond) {
for(let i = array.length - 1; i >= 0; i--) {
if(cond(array[i])) return i;
}
return -1;
}
// Gives 1 as expected
console.log(findIndexFromEnd(bigArray, (x) => x.createdAt == 2));