<searchSorted>

<searchSorted> is a General Operator component that locates values within an already sorted list: it renders the position at which each target would have to be inserted for the list to stay sorted. Unlike <indexOf>, the target need not appear in the list — this answers “where does it belong?”, not “is it there?”.

The list has to be in ascending order, and <searchSorted> checks that it is. Given values that are not in order it reports 0 instead of a position — the same “no position” it gives when target is missing — and warns, rather than returning a number that looks like a position but is not one. Equal neighbors are in order; that run is what side is about.

Write allowUnsorted on the operator and it reports where each target belongs among the values in ascending order, whatever order they are written in — so a list that is not sorted can be searched directly. The values themselves are left as they are.

Attributes and Properties

Examples

Example: where a value belongs

A target smaller than everything gives 1; a target larger than everything gives 5, one past the last index.

Example: the list has to be sorted

The first <searchSorted> gets 0 and a warning: 87 comes before 75, so no single position describes where 80 belongs. Sorting the values first — with <sort> here, though a list that is already built in order, such as a <cumulativeSum> of positive numbers, needs nothing — gives a position again. The last line gets there directly: allowUnsorted hands the ordering to the operator, which reports where 80 belongs among these values in ascending order without rearranging them. side goes on meaning what it means.

Prefer allowUnsorted when the ordering is wanted only for the search. Keep a separate <sort> when the sorted values are themselves worth showing or reusing, as $sorted is above.

This matters most when the values change as the activity runs. A list assembled from inputs can be out of order while it is being filled in, and <searchSorted> answers 0 for exactly as long as it is.

Example: sampling from a weighted population

This is the standard way to sample from a discrete distribution: accumulate the weights with <cumulativeSum>, draw uniformly from the total, then use <searchSorted> to find which bucket the draw landed in. Because every individual in the population is equally likely to be drawn, each subpopulation is selected in proportion to its size.

Example: many draws at once

Raising numSamples here does not add searches: target takes the whole list of draws and one <searchSorted> reports a subpopulation for each. Every result is still a component of its own, so the results grow with the sample — but wrapping the draws in a <repeat> to search them one at a time would build a whole operator for every draw on top of that, which stops being practical long before the sample is large enough to be interesting.

Example: side and repeated values

When the target equals several entries, side chooses which end of that run to report: left gives the first of them, right gives the position just after the last.

Example: a sorted list of words

Only an ordering is needed, not arithmetic, so a sorted text list works the same way.

Attribute Examples

Attribute Example: target

target is read the way bare children are: whitespace separates one target from the next, so target="New York" asks where two separate words belong and gets two answers. A value with a space in it is written as a <text> of its own and referenced — which is also how the sorted list is built, since <textList>Boston Chicago New York</textList> is four entries and not three.