Where does this value belong?

mediumData Structures+250 XPPractice

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.

Arguments

sortednumber[]: An array of numbers in ascending order, possibly containing duplicates.
targetnumber: The value whose insertion position is wanted.

Returns

number — The lowest index at which target could be inserted so the array stays sorted.

Examples

insertPosition([1, 3, 5, 7], 4);
// 2 — the gap between 3 and 5

insertPosition([1, 2, 2, 2, 5], 2);
// 1 — the first occurrence, not the last

Ties on the target resolve to the lowest valid index.

insertPosition([1, 2, 3], 9);
// 3 — past the end
insertPosition([], 5);
// 0 — an empty array

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.

Notes

O(log n) time, like plain binary search. This is the lower_bound from C++ and the right primitive for keeping a sorted list sorted on insertion.
The key change from binarySearch is the search space [0, length] rather than [0, length - 1], and never short-circuiting on a match — move high down to mid so duplicates settle on the lowest index.

Stuck? The javascript course covers everything this challenge needs.

Try it yourself· Edit the code, then press Run

Loading playground...

5 tests · +250 XP

Discussion

No comments yet. Be the first to say something.

All challenges108 / 150