261. Where Would It Go
Foundation1000 ms256 MBSolved by 0%
Given n distinct integers in increasing order and a value x, print the
index where x is, or where it would have to be inserted to keep the array
sorted.
1 3 5 6 x = 5 -> 2 (it is there)
1 3 5 6 x = 2 -> 1 (it would go between 1 and 3)
1 3 5 6 x = 7 -> 4 (it would go at the end)
You have already written this. It is exactly the lower bound from problem 241, and seeing that the two questions are the same question is the point of having both.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - All values are distinct and increasing.
Input
The first line contains two integers n and x.
The second line contains n distinct integers in increasing order.
Output
Print one integer: the index of x, or the index where it would be inserted.
Input4 5
1 3 5 6
Output2
Noteis present, so the answer is its own index
Input4 2
1 3 5 6
Output1
Noteis absent and belongs between two values
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.