DSA Factory
Free lessonsBinary search · Stage 0 · Halving the search · Step 2

Where would it go?

Find the first spot where a value would fit, even if it isn't there. About 10 minutes.

A question that flips once

Go along a sorted list of heights and ask at every spot: "is this person at least as tall as x?" The answers go no, no, no, then yes, yes, yes. They flip exactly once.

The first yes is where x would be placed. It is also where x is, if x is there at all, and with repeats it is the first copy.

First spot with a value at least x: is the insert position.
No yes at all? Then x goes after everything, at position n.
Where would 10 go?target = 10
2
0
5
1
5
2
9
3
14
4
14
5
20
6
25
7
lowhigh

Start with low = 0, high = 8. Position 4 holds 14, which is ≥ 10. It might be the first yes, so keep it: high = 4.

Move 1 of 3

Keep mid if it might be the answer

The answer is always somewhere between low and high, and high starts at n, one past the end. Look at the middle. If it says yes, it could be the first yes, so keep it by moving high onto it. If it says no, the first yes is later, so move low to just past it.

Stop when low and high meet. That spot is the answer.

Yes at the middle: high becomes the middle, not one less.
No at the middle: low becomes one past the middle.
In code
answers = []
for x in queries:
    low, high = 0, len(nums)
    while low < high:
        mid = (low + high) // 2
        if nums[mid] >= x:
            high = mid
        else:
            low = mid + 1
    answers.append(low)
return answers
Quick check

You want the first position with a value ≥ 3. The middle value is 3. What next?

[1, 3, 3, 3, 8] · low = 0, high = 5, mid = 2
  1. Ahigh = mid
  2. BReturn 2
  3. Chigh = mid − 1
Show the answer

high = mid. 3 ≥ 3 is a yes, but an earlier 3 might also say yes. Keep position 2 in play and look left of it.

Your problem

Where each value would go

nums is sorted from smallest to largest and may have repeats. For each value x in queries, return the first position i where nums[i] ≥ x. That's where x would be inserted to keep the list sorted. If every number is smaller than x, the answer is n.

Example
nums = [2, 5, 5, 9, 14], queries = [5, 7, 1, 20] → [1, 3, 0, 5]

0 ≤ n ≤ 2,000,000 · sorted ascending, repeats allowed · up to 2,500 queries

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding