Where does this value belong?

Inserting into a sorted list — a leaderboard, a timeline, a set of sorted filter values — needs the position, not just a yes/no answer. This is the variant of binary search that returns where a value belongs even when it is not there.

Implement insertPosition(sorted, target). sorted is an array of numbers in ascending order, possibly containing duplicates, and target is a number. Return the lowest index at which target could be inserted so the array stays sorted: that is the index of the first element greater than or equal to target, or the array's length when every element is smaller. An empty array returns 0.

Because the index must be the lowest valid one, a target that is already present returns the index of its first occurrence, not the last.

What it has to do

• Return the index of the first element greater than or equal to the target.
• Return the index of the first occurrence when the target is already present.
• Return the array length when the target is larger than every element.
• Return 0 for an empty array or a target smaller than every element.
• Halve the search range each step rather than scanning.

Your workspace