I have an array of objects that I know is sorted by one of the object properties. I want to look in the array for the object with that property equalling a specific value, so I do this:
arrOfObjects.find((obj) => obj.property === value)
However, this is an O(n) operation for an unsorted array, but O(log n) using binary search on sorted arrays.
Is there any way to tell JavaScript my array is sorted when doing a .find(), or do I have to manually implement a binary search?
There is no built-in binary search functionality in JavaScript.
Even if there was Array#find() itself cannot benefit from it, since it expects a callback that returns true or false. There is no way to determine if the expected result is before or after a given point based on a boolean result which only indicates a match.
You could implement a protoype of Array, like
Array.prototype.binaryFind = function (callbackFn, thisArg) {
// code
};
Then you need to specify a function as callback which has three states to determin the find, left or right side. An idea is to take the same approach like for sorting where an value takes the order, depending of negative, zero or positive which shows the relation of the values.
function findInObjects(key, value) {
return function (object, index, array) { //
if (object[key] === value) return 0;
if (object[key] < value) return -1;
else return 1;
}
}