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

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