Implementing binary search through nodes on an attribute

What would be the best way to do a binary search through a prosemirror document such that we could decorate the result. Here’s an example of the situation we’re working with.

Say the schema is <doc><node x=0 /><node x=5 /><node x=7 />...</doc>, where x is an attribute on each node. Say we want to find the node corresponding to attribute x=20 and decorate it (so we’ll need the position). Currently, the standard way seems to be to do a linear search using doc.descendants(). This works for the simple cases where the number of nodes is small, but once the search space becomes large enough, ideally, we’d be able to implement a binary search instead for maximum efficiency.

The roadblock we are running into is that there does not seem to be a way to derive a position from a node or its offset, and computing the offset for every binary search split is linear, so it defeats the purpose of the log(n) search altogether. Does anyone have any suggestions?

1 Like

When your document is big enough that a linear search becomes prohibitively expensive, you’re long past the point where the browser’s DOM rendering can keep up.

Optimizing repeated access is probably best done with an auxiliary data structure (that you could update incrementally in response to transactions).

Turns out we actually just ended up writing it linearly like you suggested, but it’s good to know how we’d go about optimizing it if we decide to in the future. Thanks for the help!