Tell JavaScript my array is sorted when searching for an element

Question

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?

You'll have to implement binary search. Depending on your needs, you can consider making arrOfObjects a Map, keyed by obj.property. Then you get constant access. — trincot
– trincot, Commented Apr 29, 2022 at 11:11
you'll have to write a manual search for that as find is O(n) — ahsan
– ahsan, Commented Apr 29, 2022 at 11:16
Regardless, checking if the array is sorted is O(n) so you've always got that time complexity, might just stick with .find unless there's a sorted flag after a sorting method is called. — Jack Bashford
– Jack Bashford, Commented Apr 29, 2022 at 11:16
If you want to perform a binary search, an array is a sub-optimal data structure, you should instead be using an object. — Dexygen
– Dexygen, Commented Apr 29, 2022 at 11:45

VLAZ · Accepted Answer · 2022-04-29 11:23:54Z

2

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.

answered Apr 29, 2022 at 11:23

VLAZ

29.6k9 gold badges65 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Nina Scholz · Accepted Answer · 2022-04-29 11:30:44Z

1

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

edited Apr 29, 2022 at 11:30

answered Apr 29, 2022 at 11:25

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Collectives™ on Stack Overflow

Tell JavaScript my array is sorted when searching for an element

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related