Search insert position
The list nums holds different integers in order from smallest to largest. Return the index where target belongs: the first index whose number is at least target, or len(nums) (one past the last index) when every number is smaller.
That one rule covers both cases. If target is already in the list, the answer is its own index. If it is missing, the answer is the spot where inserting target keeps the list in order. Each call must take O(log n) time, where n is the length of the list and log n is how many times n can be halved before it reaches 1.
nums = [1, 4, 6, 9], target = 5Output25 belongs between 4 and 6. It would take index 2 and push 6 to the right.
nums = [1, 4, 6, 9], target = 6Output26 is already at index 2.
nums = [1, 4, 6, 9], target = 12Output4Every number is smaller, so 12 goes at the end: index 4, the length of the list.
0 ≤ len(nums) ≤ 105
-109 ≤ nums[i], target ≤ 109
numsis sorted in ascending order with no repeats.Each call: O(log n) time.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.